题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
尝试
- 一开始以为是
i奇数的值相加，与偶数的值相加，最后比最大值，提交发现是错误的 - 然后一想就知道是一位数组的动态规划
题解
- 定义数组含义：
dp[i]设定第i房间时，所偷的钱为最大 - 找出数组元素间的关系式 => 递推公式。 题目规定：小偷不能连续偷窃相邻的房子，至少隔一个房间，
那么当我偷到第i房间的时候，我只要求出第i-2房间时跟第i-3房间时的最大值即可，i-2表示隔了一间房间，i-3表示隔了2个房间
所以递推公式为dp[i] = nums[i] + Math.max(dp[i - 3], dp[i - 2]) - 找出初始条件： 第0间自然是
nums[0], 但我们递推公式i-3和i-2理论上没有非正整数的房间，我们手动输入为0吧
var rob = function(nums) {
// dp[i] = nums[i] + Max(dp[i-3], dp[i-2])
let dp = new Map();
dp[0] = nums[0];
dp[-1] = 0;
dp[-2] = 0;
// dp(1) = nums[1] + max(dp(1-3), dp[1-2])
for(let i = 1; i < nums.length; i++) {
dp[i] = nums[i] + Math.max(dp[i-3], dp[i-2]);
}
let result = 0;
for(let i = 0; i < nums.length; i++) {
result = Math.max(result, dp[i]);
}
return result
};