LeetCode

198. 打家劫舍

思路

动态规划

dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

这里 dp[i] = Math.max(dp[i - 1], dp[i-2] + nums[i]) 的逻辑是：到第 i 个房屋能偷窃的最大值，是两种情况的较大值：

• 一种情况是不偷第 i 个房屋，那么最大值就是到第 i-1 个房屋为止能偷窃的最大值，即 dp[i - 1]；
• 另一种情况是偷第 i 个房屋，那么就不能偷第 i-1 个房屋，所以最大值是当前房屋的值 nums[i] 加上到第 i-2 个房屋为止能偷窃的最大值，即 dp[i - 2] + nums[i]。

---

PS. dp[i]定义

如果看到一些解读下的 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]) 这样的解答， 那么这里的 i 实际上是表示第i+1个房屋 因为他的数组 dp 实际上长度是 nums.length+1，并且 dp[0] = 0, dp[1] = nums[0].

题解

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  
  let dp = [nums[0], Math.max(nums[0], nums[1])]
  // 1. 确定dp[i]数组及下标含义
  // 2. 确定递推公式
  // dp[i] = max(dp[i-2] + nums[i], dp[i - 1])
  // 3. 递推初始化
  // dp[0] = nums[0]
  // dp[1] = Math.max(nums[0], nums[1])
  // 4. 确定遍历顺序，dp[i]是前面两个递推来的，从前往后遍历
  for(let i = 2; i < nums.length; i++){
    dp[i] = Math.max(dp[i - 1], dp[i-2] + nums[i])
  }
  return dp[nums.length - 1]
};

空间优化 用两个变量来存。

var rob = function(nums) {
    if(nums.length == 0) return 0;
    if(nums.length == 1) return nums[0];
    // 用两个指针做空间优化
    let pre= nums[0]
    let cur = Math.max(nums[0], nums[1])
    
    for(let i = 2; i < nums.length; i++){
        let tmp = cur;
        cur = Math.max(pre + nums[i], cur);
        pre = tmp;
    }
    return cur;
};