LeetCode刷题实战213:打家劫舍 II
共 3622字,需浏览 8分钟
·
2021-03-17 13:59
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
题意
示例
示例 1:
输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1]
输出:4
解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [0]
输出:0
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 1000
解题
var rob = function(nums) {
//特殊情况
const len = nums.length
if (len === 0) return 0
if (len === 1) return nums[0]
if (len === 2) return Math.max(nums[0], nums[1])
const rob = function(nums, start, end) {
let pMax = nums[start]
let cMax = Math.max(pMax, nums[start + 1])
for (let i = start + 2; i <= end; i++) {
console.log(i,cMax,pMax)
let tmp = cMax
cMax = Math.max((pMax +nums[i]), cMax)
pMax = tmp
}
return cMax
}
return Math.max(rob(nums, 0, len-2), rob(nums, 1, len-1))
};