198. 打家劫舍 – 力扣（LeetCode）

发布：2021年9月19日21:07:36

问题描述及示例

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]

输出：4

解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。

偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]

输出：12

解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。

偷窃到的最高金额 = 2 + 9 + 1 = 12 。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/house-robber

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

提示：

1 <= nums.length <= 100

0 <= nums[i] <= 400

我的题解（动态规划）

有关动态规划的一些通用的思路总结，可以看我下面博客中的相关总结，其中也有我写的其他动态规划题解博客的链接：

参考：

【算法-LeetCode】53. 最大子序和（动态规划初体验）_赖念安的博客-CSDN博客

不知道为什么，我一看完这道题目就在冥冥之中就觉得是要用动态规划来做，于是不自觉地往这个方面想。而且因为之前刚做过一道动态规划的题目：

参考：

【算法-LeetCode】121. 买卖股票的最佳时机（动态规划；贪心）_赖念安的博客-CSDN博客

没错，就是这篇博客，让我的粉丝数在今天（2021年9月19日）一天从昨天的5涨到了截至目前的81，几分钟前还涨了两三个。说实话，现在我还是有点疑惑为什么会这样……不过这些用户好像大部分都是刚注册CSDN的，而且都是通过用户推荐而关注我的，我倒是更希望如果有人关注我的话是看过我的文章后觉得有用才关注的。不过希望我的博客确实是能顺便给人带来了帮助吧，起码别误导了别人就好😃。

而且这道题目中所运用的

dp

数组比较特别：是一个

i×2

的二维数组（其中

i

是传入的数组参数的长度），其第二维的长度为2，分别存储当前的

两种状态

，在上面的那个股票问题中，这两种状态就是：当天持有股票和当天不持有股票。

有了上面这个题目的经验，我很快就想出了如何定义

dp

数组：同样地，我把

dp

数组定义为一个

i×2

的二维数组，且

dp[i][0]

代表小偷没偷第

i

家的财物所能盗取的最大总金额；而

dp[i][1]

代表小偷偷了第

i

家的财物所能盗取的最大总金额。

然后就是确定状态转移方程和初始化

dp

数组。这两步一般放在一起思考：

• 如果小偷不盗窃第
  
i

  家：那么小偷所盗取的财物总额就完全由他在第
  
i-1

  家时的表现所决定。

  因为小偷可能偷了第
  
i-1

  家的财物（这种情况下，小偷在盗取第
  
i

  家财物前，身上的总金额就是
  
dp[i-1][1]

  ）；

  也可能没偷第
  
i-1

  家的财物（这种情况下，小偷此时身上的总金额就是
  
dp[i-1][0]

  ）。

  只要取上面提到的两种情况中所得的总金额较大者即可。所以，就可以得到小偷不偷第
  
i

  家时所能获取到的最大总金额为
  
dp[i][0] = Math.max(dp[i-1][1], dp[i-1][0])

  。

• 如果小偷准备盗窃第
  
i

  家：因为小偷不能连续偷两家相邻的房子，所以如果小偷下了这个决定的话，就说明他没偷第
  
i-1

  家。那么此时小偷所能盗取的财物总额就是在他没偷第
  
i

  家的财物的前提下所获得的总金额（也就是
  
dp[i-1][0]

  ）再加上当前偷的这第
  
i

  家的财物。也就是：
  
dp[i][1] = dp[i-1][0] + nums[i];

  。

• 很显然，上面的动态转移方程中用到了
  
dp[i-1][0]

  和
  
dp[i-1][1]

  ，所以可以确定
  
dp[0][0]

  和
  
dp[0][1]

  是一定要我们事先赋值的。这就是
  
dp

  数组的初始化操作了。根据
  
dp

  数组的定义，我们很容易就能得到：
  
dp[0][0] = 0

  且
  
dp[0][1]=nums[0]

  。

遍历完

nums

数组之后，只要看不盗窃第

i

家财物和盗窃第

i

家财物两种情况下所能获取总金额的较大值就行了，也就是取

dp[dp.length-1][0]

和

dp[dp.length-1][1]

中的较大值即可。

详细解释请看下方注释：

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  // 创建一个nums.length × 2的dp数组，并把每个元素都初始化为0
  // 这里初始化为什么值其实都可以，因为都会被后面的计算所覆盖
  let dp = Array.from({length: nums.length}).map(
    () => Array.from({length: 2}).fill(0)
  );
  // 初始化dp数组
  dp[0][0] = 0;
  dp[0][1] = nums[0];
  // 由前到后遍历nums数组，相当于小偷沿着街道一家家地观察房子，决定要不要偷这家
  for(let i = 1; i < nums.length; i++) {
    // 小偷决定偷当前这家的财物了，说明小偷一定由于某种原因没偷前面一家的财物
    dp[i][1] = dp[i-1][0] + nums[i];
    // 小偷不准备偷当前这家的的财物了，那么此时小偷身上偷到的钱
    // 就是从之前几家偷到的钱的总额，注意，小偷不偷当前的这第i家，
    // 不说明小偷一定偷了前面的那个第i-1家，详情请看下方【补充1】
    dp[i][0] = Math.max(dp[i-1][1], dp[i-1][0]);
  }
  // 到最后哪种方案偷到的钱多，就选哪种方案（虽然我们不知道小偷具体偷了那几家）
  return Math.max(dp[dp.length-1][0], dp[dp.length-1][1]);
};


提交记录
执行结果：通过
68 / 68 个通过测试用例
执行用时：68 ms, 在所有 JavaScript 提交中击败了75.55%的用户
内存消耗：38 MB, 在所有 JavaScript 提交中击败了12.81%的用户
时间：2021/09/19 21:11

相关补充

【

补充1

】

注意，上面说到：小偷没偷第

i

家，不代表小偷一定偷了第

i-1

家。如果简单地认为既然小偷没偷第

i-1

家就一定会偷第

i

家，那就说明这个小偷“目光短浅”。

比如输入这个用例：

[2,1,1,2]

。如果以上面那种“目光短浅”的偷法施行盗窃，那么小偷就会这样偷：先偷第

1

家，再偷第

3

家，总共获得

2+1=3

的总金额。但是很明显，先偷第

1

家，再偷第

4

家，就可以总共获得

2+2=4

的总金额。

为什么会出现这种情况呢？主要就是那种“目光短浅”的偷法没有充分考虑到这种偷法会因为贪图眼前的一些芝麻（当前这第

i

家的财物比较少），而错过后面可能遇到的西瓜（第

i+1

家的财物可能会比第

i

家多），而这种“错过”是一种被迫的错过，因为小偷得保证不触发警报的话就必须跳过第

i+1

家。

泪目，小偷不来光顾我家竟是因为这！背后原因令人暖心……

所以说，如果小偷想要最后偷到最多的财物，必须战略性地放弃盗窃其中的某些房子。看来当小偷也得要有一定的谋略才行啊……🤣

【

补充2

】

注意，这种动态规划所得出的方案是无法确定小偷具体偷了那几家的财物的，因为我们只需关注最后的结果是否为最佳，而不关心其中的过程。

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

更新：2021年9月19日21:12:12

参考：

打家劫舍 – 打家劫舍 – 力扣（LeetCode）

【更新结束】

有关参考

更新：2021年9月19日21:12:58

参考：

【算法-LeetCode】53. 最大子序和（动态规划初体验）_赖念安的博客-CSDN博客


参考：

【算法-LeetCode】121. 买卖股票的最佳时机（动态规划；贪心）_赖念安的博客-CSDN博客