打家劫舍问题如何用动态规划求解？（LeetCode 198）

简化版

沿街一排房子各有金额，不能偷相邻两家（会报警），求能偷到的最大金额。设 dp[i] 为「偷到第 i 家为止能拿的最大金额」，对第 i 家只有两个选择：不偷（金额沿用 dp[i-1]）或偷（不能碰 i-1，金额是 dp[i-2] + nums[i]），取两者较大——dp[i] = max(dp[i-1], dp[i-2] + nums[i])。同样只依赖前两项，可状态压缩到 O(1) 空间。

详细版

int rob(int[] nums) {
    int prev = 0, cur = 0;           // prev = dp[i-2], cur = dp[i-1]
    for (int x : nums) {
        int next = Math.max(cur, prev + x); // 不偷 vs 偷这家
        prev = cur;
        cur = next;
    }
    return cur;                       // dp[n-1]
}

状态：dp[i] = 考虑前 i+1 家（下标 0..i）能偷到的最大金额。
转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
- 不偷第 i 家：结果就是前 i-1 家的最优 dp[i-1]；
- 偷第 i 家：不能偷 i-1 家，只能接 dp[i-2]，再加上 nums[i]。
初始化：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])（代码里用 prev=cur=0 起步等价处理）。
状态压缩：只用前两项，两个变量滚动，空间 O(1)。

完整版教学

一、问题与「偷或不偷」的决策

打家劫舍：一排房子 nums，相邻的不能同时偷，求最大总金额。例如 [2,7,9,3,1]，最优是偷第 0、2、4 家（2+9+1=12）。

这是线性 DP 里「选或不选」模型的代表：遍历到每一家，都面临「偷它 / 不偷它」的二选一，且这个选择受「相邻不能都偷」约束。DP 要做的，就是把这个逐家决策的最优结果递推出来。

二、状态定义与转移方程

定义状态：dp[i] = 「只考虑前面到第 i 家（下标 0 到 i），且遵守不偷相邻规则，能偷到的最大金额」。

推转移方程——照例盯住「第 i 家怎么处理」，两种互斥选择：

不偷第 i 家：那第 i 家不贡献金额，最大值就等于「前 i-1 家的最优解」dp[i-1]。
偷第 i 家：那第 i-1 家绝不能偷（相邻约束），所以只能在「前 i-2 家的最优解」dp[i-2] 基础上，再加第 i 家的钱 nums[i]。

两者取最大：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])
          └─不偷─┘   └───偷第 i 家───┘

关键点：偷第 i 家时接的是 dp[i-2] 而不是 dp[i-1]——因为 dp[i-1] 可能包含了偷第 i-1 家的方案，那样就违反「相邻不能都偷」了。跨过 i-1、接 i-2，正是这道题的精髓。

三、初始化与遍历

dp[0] = nums[0]：只有一家，偷它。
dp[1] = max(nums[0], nums[1])：两家只能偷一家，取金额大的。
从 i=2 开始套转移方程往后递推，答案是 dp[n-1]。

代码里用 prev=0, cur=0 起步、边遍历边滚动，是把上面初始化融进循环的等价简洁写法（第一轮 next=max(0, 0+nums[0])=nums[0]，自然得到 dp[0]）。

四、状态压缩

dp[i] 只依赖 dp[i-1] 和 dp[i-2]，所以又能用两个变量滚动代替整个数组：prev 记 dp[i-2]、cur 记 dp[i-1]，每轮算出 next 后向前滚。空间从 O(n) 降到 O(1)，和爬楼梯一个套路。

压缩前先写出 prev2=dp[i-2]、prev1=dp[i-1] 的语义。当前值必须用旧的二者计算，再整体向前滚动；若先覆盖 prev1，就会丢掉“不偷当前房”所依赖的前缀最优值。

五、扩展：环形（打家劫舍 II）与树形（III）

打家劫舍有两个经典进阶，常连着考：

打家劫舍 II（环形，LeetCode 213）：房子首尾相连成环，第一家和最后一家也算相邻。处理办法是拆成两个线性问题：一种「偷第一家、不偷最后一家」即只考虑 nums[0..n-2]，另一种「不偷第一家、可偷最后一家」即 nums[1..n-1]，各自跑一遍上面的线性 DP，取两者最大。这样规避了「首尾同时偷」。
打家劫舍 III（树形，LeetCode 337）：房子排成二叉树，父子节点不能同时偷。改用树形 DP：对每个节点用后序遍历返回两个值——{偷该节点的最大值, 不偷该节点的最大值}，父节点根据子节点的这对值组合。思想仍是「选或不选」，只是载体从数组变成树。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：处理到第 i 间房的最优值只需知道偷 i 时不能偷 i-1，以及不偷 i 时继承前缀最优。

转移过程是：dp[i]=max(dp[i-1], dp[i-2]+nums[i])，滚动变量分别保存前一项与前两项。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：[2,7,9,3,1] 依次得到 2,7,11,11,12，最优选择 2+9+1。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：空数组与单元素要单独对应；环形版本拆成不含首或不含尾两条线性区间；树形版本每节点返回偷/不偷两态。

核对项	本题答案
复杂度	O(n) 时间，O(1) 额外空间
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：每次看到金额更大就偷。 局部大值可能阻断两侧组合，需比较两种前缀状态。
误区：环形版本直接跑一次线性 DP。 首尾相邻，必须排除同时选择。
误区：滚动变量更新顺序无所谓。 要先保存新值，再把旧 prev1 移到 prev2。
追问：为什么只需前两项？ 约束只连接相邻房，选择 i 只影响 i-1。
追问：如何恢复被偷下标？ 保留完整 dp 后从末尾比较 dp[i] 与 dp[i-1] 回溯。
追问：金额允许负数怎么办？ 若允许不偷任何房，初值应保证结果至少为 0。

九、加强记忆

打家劫舍：dp[i] = 到第 i 家的最大金额，第 i 家偷或不偷二选一——不偷则 dp[i-1]，偷则 dp[i-2]+nums[i]（跨过相邻的 i-1、接 i-2 是关键），取最大：dp[i]=max(dp[i-1], dp[i-2]+nums[i])。只依赖前两项 → 两变量滚动，O(1) 空间。扩展：环形（拆成 [0..n-2] 与 [1..n-1] 两次线性取最大）、树形（后序返回「偷/不偷」两值）。

简化版

详细版