打家劫舍 · House Robber

线性 DP · 滚动变量

相邻两间不能同时偷。诀窍不是公式，而是让每间房都比一比「偷它」与「不偷它」两条路，谁的总收益大就走谁。

输入 · nums

偷

i=0

跳过

i=1

偷

i=2

跳过

i=3

偷

i=4

最优方案：偷下标 0, 2, 4 = 2 + 9 + 1

最大金额

不偷相邻 · 全局最优

时间 O(n) · 一次遍历空间 O(1) · prev2 / prev1 两个滚动变量核心：cur = max(prev1, prev2 + nums[i])

题目Step 1 / 11

题目输入与约束

题目

一排房子 nums = [2, 7, 9, 3, 1]，每间藏着现金。相邻两间装了联动报警器：一旦同时被偷就会触发。问：在不偷相邻两间的前提下，最多能偷到多少？

Go 解法 · 与状态同步

高亮行: 1

1func rob(nums []int) int {
2    prev2, prev1 := 0, 0
3    for i := 0; i < len(nums); i++ {
4        // 不偷 i → prev1 ; 偷 i → prev2 + nums[i]
5        cur := max(prev1, prev2+nums[i])
6        prev2 = prev1
7        prev1 = cur
8    }
9    return prev1
10}

第 5 行就是核心： cur = max(prev1, prev2 + nums[i]) —— 不偷取 prev1，偷取 prev2 + nums[i]。

机器状态 · 这一帧的全部变量

—

nums[i]

—

prev2 · 上上间最优

prev1 · 上一间最优

cur · 当前房后最优

—

滚动规则

prev2 ← prev1 ; prev1 ← cur

不变量

在处理完第 i 间房后， prev1 始终表示 nums[0..i] 范围内能偷到的最大金额。

正因为这条不变量，遍历到最后一间时 prev1 就是整段数组的全局最优，直接返回即可。 prev2 则慢一拍，表示 nums[0..i-1] 的最大金额。

执行轨迹 · 每间房的 Skip / Rob

点击行跳转

i	nums[i]	prev2	prev1	skip = prev1	rob = prev2 + nums[i]	cur = max	选择
0	2	0	0	0	2	2	偷
1	7	0	2	2	7	7	偷
2	9	2	7	7	11	11	偷
3	3	7	11	11	10	11	不偷
4	1	11	11	11	12	12	偷

面试 30 秒答题模板

相邻不能同时偷，所以不能贪心，要做线性 DP：定义 dp[i] 为偷 nums[0..i] 的最大金额。每间房只有两种选择 —— 不偷它，收益是 prev1；偷它，因为不能碰 i-1，只能接上 prev2，收益是 prev2 + nums[i]。于是 cur = max(prev1, prev2 + nums[i])，再滚动 prev2 ← prev1、prev1 ← cur。遍历结束返回 prev1 = 12。状态只依赖前两项，所以用两个变量代替整张表，时间 O(n)、空间 O(1)。

常见误区 · 别再翻车

贪心选当前最大的房子
见钱就拿会被相邻约束锁死。如反例 [2,1,1,2]：先抢开头的 2 反而只剩 3，跳过中间偷首尾才有 4。必须比较两种未来，不能只看眼前最大。
prev1 / prev2 更新顺序写反
必须先 prev2 ← prev1，再 prev1 ← cur。若先写 prev1 ← cur，prev2 就会读到被覆盖后的新值，下一轮的「上上间」全错。两行顺序不能交换。
忘了空数组返回 0
nums 为空时不会进入循环，prev1 仍是初始的 0，正好就是答案。初始化成 0 而不是 nums[0]，才能自然覆盖空数组与单间房两种边界。

迁移练习 · 同一套「偷 / 不偷」思路

LC213House Robber II · 环形

房子首尾相邻成环，nums[0] 与 nums[n-1] 不能同时偷。破环：拆成两个 LC198 —— 偷 nums[0..n-2] 或偷 nums[1..n-1]，两次线性 DP 取大。注意 n==1 的边界。

LC337House Robber III · 二叉树

房子排成二叉树，相邻变成父子。每个节点同样有偷 / 不偷两种状态：用后序遍历让每个节点返回 [偷该点, 不偷该点] 两个值，父节点再据此组合，本质还是「两种选择取大」。