LeetCode 198. 打家劫舍

题目核心

一排房屋中，每间房都放着一定金额的钱，数组 nums 中的 nums[i] 就是第 i 间房里的金额。

相邻的两间房不能在同一晚偷，求最多能够偷到多少钱。

例如：

nums = [2, 7, 9, 3, 1]

可以选择第 0、2、4 间房：

2 + 9 + 1 = 12

也可以选择第 1、3 间房：

7 + 3 = 10

所以答案是 12。

解题思考过程

第一步：理解问题

这是一个典型的动态规划问题。每个决策（偷或不偷）会影响后面的决策。

第二步：暴力解法（递归）

最直接的思路：对于每间房，有两种选择：偷或不偷。

偷第i间房：不能偷第i-1间，总金额 = nums[i] + 偷前i-2间的最大金额
不偷第i间房：可以偷第i-1间，总金额 = 偷前i-1间的最大金额

递归公式：f(i) = max(f(i-1), nums[i] + f(i-2))

但这个方法有大量重复计算：

f(4) = max(f(3), nums[4] + f(2))
f(3) = max(f(2), nums[3] + f(1))
f(2) = max(f(1), nums[2] + f(0))
...

时间复杂度：O(2^n)，指数级，太慢了。

第三步：优化（记忆化搜索）

既然有重复计算，那就把计算结果存起来，下次直接用。

用 memo[i] 记录前i间房能偷的最大金额
如果 memo[i] 已经计算过，直接返回
否则计算并存入 memo[i]

时间复杂度：O(n)，每个子问题只计算一次。

第四步：优化（动态规划）

记忆化搜索是自顶向下的，能不能改成自底向上的迭代方式？

dp[i] = max(dp[i-1], nums[i] + dp[i-2])

初始化：
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

第五步：空间优化

观察动态规划的公式，每次只需要 dp[i-1] 和 dp[i-2]，不需要整个 dp 数组。

用两个变量代替数组：
prev_prev = dp[i-2]
prev = dp[i-1]
curr = max(prev, nums[i] + prev_prev)

然后迭代更新：
prev_prev = prev
prev = curr

空间复杂度从 O(n) 降到 O(1)！

第六步：最终代码

时间复杂度：O(n)
空间复杂度：O(1)

这是最优解法！

2 + 9 + 1 = 12

所以答案是 12。

这道题的重点不是找出金额最大的几间房，而是处理“选了当前房，就不能选下一间房”这个限制。

核心思路：每间房只有选和不选

走到第 i 间房时，只有两种选择。

选择当前房

如果偷第 i 间房，就不能偷相邻的第 i + 1 间房，所以下一次只能从第 i + 2 间房继续：

nums[i] + dfs(i + 2)

不选择当前房

如果不偷第 i 间房，就可以直接考虑下一间房：

dfs(i + 1)

两种选择中取金额更大的一种：

dfs(i) = Math.max(nums[i] + dfs(i + 2), dfs(i + 1));

这里的 dfs(i) 表示：

从第 i 间房开始考虑，最多能够偷到多少钱

当前代码需要改进的地方

当前代码已经写出了正确的“选或不选”递归关系，也创建了 mem 数组：

const mem = new Array(nums.length).fill(0);

但是递归中没有读取和保存 mem[i]，因此相同位置会被反复计算。

例如计算 dfs(0) 时会需要 dfs(2)，计算 dfs(1) 时也会需要 dfs(2)。数组越长，重复计算就越多，时间复杂度会接近 O(2^n)，无法通过较大的测试数据。

另外，原代码中的 res 没有使用 let 或 const 声明：

res = Math.max(...);

这会产生意外的全局变量，在严格模式下还会直接报错。其实这里不需要额外的 res，把结果保存到 mem[i] 即可。

解法一：记忆化搜索

在普通递归的基础上，用 mem[i] 保存 dfs(i) 已经算出的答案。以后再次遇到相同的 i，直接返回保存的结果。

var rob = function (nums) {
  const mem = new Array(nums.length).fill(-1);

  const dfs = (i) => {
    if (i >= nums.length) {
      return 0;
    }

    if (mem[i] !== -1) {
      return mem[i];
    }

    const choose = nums[i] + dfs(i + 2);
    const skip = dfs(i + 1);

    mem[i] = Math.max(choose, skip);
    return mem[i];
  };

  return dfs(0);
};

为什么只需要返回 dfs(0)

dfs(0) 的意思是从第 0 间房开始考虑，它本身已经包含了两种情况：

偷第 0 间房
不偷第 0 间房，改为考虑第 1 间房

因此不需要再写：

Math.max(dfs(0), dfs(1));

因为 dfs(1) 已经包含在 dfs(0) 的“不选第 0 间房”这条分支中了，直接返回 dfs(0) 就够了。

计算过程

以 nums = [2, 7, 9, 3, 1] 为例。

从最后一间房向前理解会更直观：

dfs(4) = max(偷 1 + dfs(6), 不偷 1 + dfs(5))
       = max(1, 0)
       = 1

dfs(3) = max(偷 3 + dfs(5), 不偷 3 + dfs(4))
       = max(3, 1)
       = 3

dfs(2) = max(偷 9 + dfs(4), 不偷 9 + dfs(3))
       = max(10, 3)
       = 10

dfs(1) = max(偷 7 + dfs(3), 不偷 7 + dfs(2))
       = max(10, 10)
       = 10

dfs(0) = max(偷 2 + dfs(2), 不偷 2 + dfs(1))
       = max(12, 10)
       = 12

最终答案是 12。

为什么 mem 使用 -1 初始化

房屋金额可能为 0，所以某个位置的正确答案也可能是 0。

如果用 0 表示“还没有计算”，就无法区分：

这个位置还没算过
这个位置算过了，答案刚好是 0

题目中的金额不会是负数，因此可以安全地用 -1 表示“尚未计算”。

复杂度

• 时间复杂度：O(n)，每个位置只会被真正计算一次。
• 空间复杂度：O(n)，mem 数组和递归调用栈都需要空间。

解法二：动态规划

记忆化搜索是从前往后提出问题，再通过递归得到答案；动态规划则可以直接从前往后计算。

定义：

dp[i] 表示只考虑前 i 间房时，最多能偷到多少钱

考虑第 i 间房时仍然只有两种选择：

不偷当前房：dp[i - 1]
偷当前房：dp[i - 2] + nums[i]

因此状态转移为：

dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

由于每次只会用到前两个状态，可以把数组压缩成两个变量：

var rob = function (nums) {
  let twoBefore = 0;
  let oneBefore = 0;

  for (const money of nums) {
    const current = Math.max(oneBefore, twoBefore + money);
    twoBefore = oneBefore;
    oneBefore = current;
  }

  return oneBefore;
};

变量含义如下：

twoBefore：考虑到前两间房时的最大金额
oneBefore：考虑到前一间房时的最大金额
current：考虑到当前房时的最大金额

这个写法的时间复杂度是 O(n)，空间复杂度是 O(1)。

两种解法对比

解法	时间复杂度	空间复杂度	特点
记忆化搜索	O(n)	O(n)	更贴近“选或不选”的思考过程
动态规划 + 空间压缩	O(n)	O(1)	空间更优，适合最终提交

第一次理解这道题时，可以先掌握记忆化搜索。理解 dfs(i) 的含义和两种选择后，再写动态规划会容易很多。