题目

题目来源：力扣（LeetCode）

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

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


示例 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 。

思路分析

动态规划

1、确定 dp 数组以及下标的定义

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

2、确定递推公式

决定 dp[i] 的因素就是第 i 房间偷还是不偷:

如果偷第 i 房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第 i - 1 房一定是不偷的，找出下标 i - 2 (包括i - 2)以内的房屋，最多可以偷窃的金额为 dp[i - 2] 加上第 i 房间偷到的钱。

如果不偷第i房间，那么 dp[i] = dp[i - 1]，即偷第 i - 1 间房，(注意这里是考虑，并不是一定要偷 i - 1 房)。

然后 dp[i] 取最大值，即 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

3、dp数组如何初始化

从递推公式 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])可以看出，递推公式的基础就是dp[0] 和 dp[1] 。

从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1] 就是 nums[0] 和 nums[1] 的最大值即：
dp[1] = max(nums[0], nums[1]);

4、确定遍历顺序

dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

代码实现

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function(nums) {
  6.     const len = nums.length;
  7.     if(len == 0)
  8.         return 0;
  9.     const dp = new Array(len + 1);
  10.     dp[0] = 0;
  11.     dp[1] = nums[0];
  12.     for(let i = 2; i <= len; i++) {
  13.         dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
  14.     }
  15.     return dp[len];
  16. };

二维数组解法

  1. var rob = function (nums) {
  2.   let n = nums.length;
  3.   // 状态数组
  4.   // i：每一间屋子 x：当前屋子不偷的金额 y：当前屋子偷的金额
  5.   // 二维数组 dp[i][x，y]
  6.   let dp = new Array(n).fill(0).map(item => item = new Array(2));
  7.   // 0: 不偷 1: 偷 第一间屋子偷 或者 不偷 赋值
  8.   dp[0][0] = 0, dp[0][1] = nums[0];
  9.   for (let i = 1; i < n; i++) {
  10.     // 当前屋子不偷，那上一间屋子可以偷，也可以不偷，所以取上间屋子两者最大值
  11.     dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
  12.     // 当前屋子偷，那上一间屋子就不能偷，不偷的值 + 当前屋子的值
  13.     dp[i][1] = dp[i - 1][0] + nums[i];
  14.   }
  15.   // 取 最后一项偷或者不偷的最大值
  16.   return Math.max(dp[n - 1][0], dp[n - 1][1]);
  17. };

考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var rob = function (nums) {
  6.   if (nums == null || nums.length == 0) {
  7.     return 0;
  8.   }
  9.   let length = nums.length;
  10.   if (length == 1) {
  11.     return nums[0];
  12.   }
  13.   let first = nums[0], second = Math.max(nums[0], nums[1]);
  14.   for (let i = 2; i < length; i++) {
  15.     let temp = second;
  16.     second = Math.max(first + nums[i], second);
  17.     first = temp;
  18.   }
  19.   return second;
  20. };

参考阅读：
https://leetcode-cn.com/problems/house-robber/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dong-ezvt3/ https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/ https://leetcode-cn.com/problems/house-robber/solution/hua-jie-suan-fa-198-da-jia-jie-she-by-guanpengchn/