你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金，影响力偷窃的唯一制约因素就是相邻的房屋装有相互联通的防盗系统。如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例一
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例二
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
自己做题过程中的错误思路：
- 就是奇数项和、偶数项和的最大数。其实不然，如果遇到
[2, 1, 1, 2]这种情况就是4，而不是奇数项和偶数项和的最大数3
纠正后的解题思路：
-
設置缓存最大和数组
max，缓存每一个下标的为结尾的最大结果和max[i]（能够偷窃到的最高金额） - 設置布尔值变量
flag,如果flag为true，说明前一项没有添加进去，现在这一项可以直接添加，否则，比较max[i-2] + nums[i]和max[i-1]，取大的作为下标i的最大结果和 - 返回最后一项的
max[i]，就是所求的结果
编码实现
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length <= 0) {
return 0
}
if (nums.length < 2) {
return nums[0]
}
let max = [nums[0]]
max[1] = nums[0] > nums[1] ? nums[0] : nums[1]
let flag = false
for (let i = 2; i < nums.length; ++i) {
if (flag) {
let curr = max[i-1]
max[i] = curr + nums[i]
flag = false
} else {
if (max[i-2] + nums[i] > max[i-1]) {
max[i] = max[i-2] + nums[i]
} else {
max[i] = max[i-1]
flag = true
}
}
}
return max[nums.length - 1]
};
正确的解题思路：
动态规划的思想：
- 初始状态方程：缓存数组：
f[0]和f[1] - 状态转移方程：
f[i] = max(f[i-2] + nums[i], f[i-1])
思路：
- 取出初始状态，
f[0]和f[1] - 从数组第三项开始遍历数组，对每一项运用状态转移方程得出当前项的最大值
f[i] = max(f[i-2] + nums[i], f[i-1]) - 返回
f数组的最后一项
编码实现：
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length <= 0) {
return 0
}
if (nums.length < 2) {
return nums[0]
}
let max = [nums[0]]
max[1] = Math.max(nums[1], nums[0])
for (let i = 2; i < nums.length; ++i) {
max[i] = Math.max(max[i-2] + nums[i], max[i-1])
}
return max[nums.length - 1]
};