本文概览：本文讲解打家劫舍的核心思路：dp[i] 表示偷到第 i 房的最大金额，偷或不偷第 i 房两种情况取最大，滚动变量优化到 O(1) 空间

一、题目

打家劫舍 题目图片

二、题目分析

1. 题目要求

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

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

例子：nums = [1, 2, 3, 1]

1
2
3
4
5
6
7
房屋编号: 0  1  2  3
金额:    1  2  3  1

偷 0 号和 2 号（不相邻）：1 + 3 = 4
偷 1 号和 3 号（不相邻）：2 + 1 = 3
偷 0 号和 3 号（不相邻）：1 + 1 = 2
偷 0 号、2 号（最优）→ 最高金额 = 4

核心制约：偷了第 i-1 房，则第 i 房必不能偷（相邻触发警报）。

2. 怎么判断这是动态规划问题？

这题直接去想很难想：偷窃方案是 0 号偷不偷、1 号偷不偷...的组合，n 间房就是 2ⁿ 种组合，枚举肯定不现实。

我们换个角度，从后往前思考：偷到第 i 房的最大金额，和偷到前面房屋的最大金额，有没有关系？

试着站在第 i 房往回看：它偷不偷，完全取决于第 i-1 房有没有被偷——相邻的决策之间相互影响。再想一层：如果我偷了第 i 房，那金额就是"前面推进到第 i-2 房的最大金额 + nums[i]"——大问题的答案，可以由更小规模的问题的答案组合出来。

这个味道很熟悉了：元素前后有关系，且算的是总数（最优值）——和爬楼梯"到达第 i 阶的方法数由 i-1、i-2 推出来"是同一类结构，大概率就是动态规划类题目。

再验证一下无后效性：只要知道"偷到第 i-1 房为止的最大金额"，第 i 房怎么选就与更早的细节无关——具体前面怎么偷的、走的哪条组合，都不影响后续决策。满足，可以用 DP。

（动态规划问题的完整特征见上一篇《动态规划入门》。）

3. 需要解决哪几个问题？

确定了用动态规划，接下来要解决两个问题：

问题一：状态数组 dp[] 怎么定义？——dp[i] 表示什么？

问题二：转移方程是什么？——dp[i] 怎么由更小的状态推出来？

三、思路概览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int rob(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    // 当前房屋的最大金额
    int cur = 0;
    // 上一个房屋的最大金额
    int pre = 0;
    for (int num : nums) {
        int temp = cur;
        cur = Math.max(cur, pre + num);
        pre = temp;
    }
    return cur;
}

思路简要说明：

  1. 转移方程：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])，不偷第 i 房 or 偷第 i 房，取大者
  2. 空间优化：dp[i] 只和 dp[i-1]、dp[i-2] 有关，两个滚动变量（cur、pre）就够，不需要数组
  3. 遍历方向：从头往后遍历，一遍算出整个 dp，最后 cur 就是 dp[n-1]
  4. **时间复杂度 O(n)**，空间复杂度 O(1)

四、思路详解

第一步：解决状态定义——dp[i] 表示什么？

dp[i] 表示偷盗到第 i 房时（考虑完 0..i 这些房）的偷盗总金额最大值。

为什么这样定义？因为"考虑完前 i+1 间房的最大金额"就是原问题在规模 i 下的形态：原问题是"考虑完所有 n 间房"（即 dp[n-1]），把它缩小就是"考虑完前 i+1 间房"（即 dp[i]）——大问题和小问题形式完全一样，只是规模不同，这正是 DP 状态定义的要求。

第二步：解决转移方程——直接看第 i 房，只有两种情况

偷盗方案千千万（0 号偷不偷、1 号偷不偷...的组合），但站在第 i 房往回看，最终方案在第 i 房这里的"落脚"只有两种：

情况一：不偷第 i 房

不偷它，金额没有任何变化，偷到第 i 房的总金额就等于偷到第 i-1 房的：

1
dp[i] = dp[i-1]

情况二：偷第 i 房

偷了第 i 房，第 i-1 房必不能偷（否则报警）。那偷盗金额是多少？是偷到第 i-2 房的总金额 + 第 i 房的金额：

1
dp[i] = dp[i-2] + nums[i]

两种情况选最大的（不偷不一定亏——可能 nums[i] 很小但 dp[i-1] 很大；偷也不一定赚——要看 dp[i-2] + nums[i] 能不能超过 dp[i-1]）：

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

和爬楼梯"最后一步从哪来"是同一个分析手法：不枚举完整方案，只枚举最后一步的选择。最后一步定了，前面部分就交给同结构的小问题（dp[i-1] 或 dp[i-2]）。

为什么两种情况"不重不漏"？ 偷或不偷，二选一，没有第三种；且两种情况的计算互不干扰，直接取 max 即可。

初始条件（转移方程推不出来的起点）：

  • dp[0] = nums[0]（只有第 0 房，偷它）
  • dp[1] = Math.max(nums[0], nums[1])（前两房只能偷一个，偷金额大的）

第三步：为什么偷第 i 房时是 dp[i-2] 而不是别的？

偷了第 i 房，i-1 被锁死，那金额应该是"dp[i-2] + nums[i]"——这里有个容易犯的错：会不会觉得"从 i-2 之前随便哪房接过来"？

不会。因为 **dp[i-2] 已经是"考虑完 0..i-2 这些房的最优解"**——它内部已经把"i-2 偷不偷、更早怎么偷"全部安排到最优了。我们不需要关心 dp[i-2] 里面的方案长什么样，只需要知道它是最优的（无后效性）。

这正是状态定义的威力：一个格子浓缩了前面所有决策的最优结果。

第四步：滚动变量怎么工作的？

dp[i] 只依赖 dp[i-1] 和 dp[i-2]，所以数组可以砍掉，只留两个变量：

  • cur：当前算到的最大金额（对应 dp[i-1]，进入第 i 间前）
  • pre：更前一个的最大金额（对应 dp[i-2]）

循环里三行代码的流转：

1
2
3
int temp = cur;                          // 暂存旧的 dp[i-1]
cur = Math.max(cur, pre + num);          // 算新的 dp[i]：max(不偷, 偷)
pre = temp;                              // 旧的 dp[i-1] 变成下一轮的 dp[i-2]

每走一间房，两个变量就往前滚一格，遍历结束时 cur 就是 dp[n-1]。

初始值为什么是 cur=0、pre=0？ 对应"还没偷任何房，金额 0"。第一轮：cur = max(0, 0 + nums[0]) = nums[0]，正好等于 dp[0]；第二轮：cur = max(nums[0], 0 + nums[1]) = max(nums[0], nums[1])，正好等于 dp[1]——和标准的初始条件吻合，而且空数组时直接返回 0，不用特判。

完整执行过程

以 nums = [1, 2, 3, 1] 为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
初始：cur = 0, pre = 0

num=1（第0房）：
  temp = 0
  cur = max(0, 0 + 1) = 1     ← dp[0] = 1
  pre = 0

num=2（第1房）：
  temp = 1
  cur = max(1, 0 + 2) = 2     ← dp[1] = max(1, 2) = 2
  pre = 1

num=3（第2房）：
  temp = 2
  cur = max(2, 1 + 3) = 4     ← dp[2] = max(dp[1], dp[0]+3) = 4
  pre = 2

num=1（第3房）：
  temp = 4
  cur = max(4, 2 + 1) = 4     ← dp[3] = max(dp[2], dp[1]+1) = 4
  pre = 4

返回 cur = 4 ✓
（对应偷第 0 房和第 2 房：1 + 3 = 4）

注意最后一步：dp[3] 时偷第 3 房的方案是 dp[1] + 1 = 3，不偷是 dp[2] = 4，max 取 4——第 3 房金额太小，最优方案直接跳过它。

再走一个 nums = [2, 7, 9, 3, 1] 的例子：

1
2
3
4
5
6
7
8
9
10
初始：cur = 0, pre = 0

num=2：cur = max(0, 0+2) = 2, pre = 0        ← dp[0]=2
num=7：cur = max(2, 0+7) = 7, pre = 2        ← dp[1]=7
num=9：cur = max(7, 2+9) = 11, pre = 7       ← dp[2]=11（偷0、2）
num=3：cur = max(11, 7+3) = 11, pre = 11     ← dp[3]=11（跳过第3房）
num=1：cur = max(11, 11+1) = 12, pre = 11    ← dp[4]=12（偷0、2、4）

返回 cur = 12 ✓
（2 + 9 + 1 = 12）

复杂度分析

**时间复杂度 O(n)**：一遍遍历，每间房常数次比较。

**空间复杂度 O(1)**：只用两个滚动变量。这是"dp[i] 只依赖前两项"带来的红利——和爬楼梯、斐波那契的空间优化完全一样。

五、总结

打家劫舍的核心思路：

  1. 判断题型：元素前后有关系（相邻不能同偷）+ 算总数（最高金额）→ 动态规划
  2. 状态定义：dp[i] = 偷到第 i 房时的最大总金额
  3. 转移方程：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])，不偷 or 偷，取大者
  4. 空间优化：只依赖前两项 → 两个滚动变量，O(1) 空间
  5. 初始值技巧：cur=0、pre=0 起步，第一二轮自动滚出 dp[0]、dp[1]，连边界特判都省了

和入门两题的关系：爬楼梯的 dp[i] = dp[i-1] + dp[i-2] 是"两种来路相加"（方案数），打家劫舍的 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 是两种选择取最大（最优值）——结构同源，只是一个数方案、一个求最优。这也是 DP 最常见的两大形态。