Skip to content

LeetCode

198. 打家劫舍

image.png

思路

动态规划

image.png

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].image.pngimage.pngimage.png

题解

typescript
/**
 * @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]
};

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

image.png

typescript
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;
};