LeetCode 198. 打家劫舍：相邻约束下的动态规划

打家劫舍（LeetCode 198，Medium）是动态规划的「相邻约束」教科书：一排房子，每个房子里有不同金额，不能偷相邻的两家，求能偷到的最高金额。它在本库 DP 系列里的位置很讲究：比《爬楼梯》（只有一种转移）多了「偷或不偷」的选择结构，比《零钱兑换》（多枚硬币的枚举）少了一层维度——它是理解「状态定义决定转移方程」的最佳样本：状态定义换一个说法，整道题的难度感都会变。

状态设计：dp[i] 的两种定义与转移

定义一：dp[i] = 考虑前 i 个房子能偷到的最大金额。转移围绕「第 i 个房子偷不偷」：偷它——第 i-1 个不能偷，金额是 dp[i-2] + nums[i]；不偷它——金额是 dp[i-1]。取两者最大：dp[i] = max(dp[i-1], dp[i-2] + nums[i])，边界 dp[0] = nums[0]、dp[1] = max(nums[0], nums[1])。答案 dp[n-1]。这个定义的优雅之处：dp[i-1] 本身已经包含了「第 i-1 个偷了或没偷」的两种情况——「不偷第 i 个」的最大值自动等于 dp[i-1]，不需要显式讨论；转移方程的两项，恰好对应「偷/不偷」的分支，且各自引用的子问题（i-2 与 i-1）都满足「无后效性」。

定义二（空间优化的视角）：观察转移只依赖 dp[i-1] 与 dp[i-2]——两个变量滚动即可，空间从 O(n) 压到 O(1)：

def rob(nums: list[int]) -> int:
    prev, curr = 0, 0        # prev = dp[i-2], curr = dp[i-1]
    for x in nums:
        prev, curr = curr, max(curr, prev + x)
    return curr

三行核心，就是这道题的全部。读法：走到第 i 个房子时，max(curr, prev + x) 在「不偷它（继承 curr）」与「偷它（prev 加上它的钱）」之间取大——循环不变量：进入第 i 轮时，curr 是前 i 个房子的最优解。

深层联系：它其实是「带约束的最大子序列和」

把视角拉高，打家劫舍的本质是：在序列上选一个子集，要求任意两元素不相邻，最大化元素和——这是「最大子序列和」加了「不相邻」约束的版本。这个视角统一了一族问题：打家劫舍 II（房子围成环——首尾相邻，解法是「拆成两个线性问题」：分别算「不偷第一家」与「不偷最后一家」的线性版本取大，本篇的滚动解法直接复用）；打家劫舍 III（房子是二叉树——相邻约束变成父子约束，回到本库《二叉树最大路径和》的树形 DP：「返回状态向量（偷/不偷该节点），父节点用子节点状态转移」）；以及删除获得点数类的变形（把「金额」换成「价值函数」后同构）。DP 学习的方法论在此显形：同一族的问题，核心约束只有一个（相邻不相容），学会了「约束如何进入转移方程」，一族题就都会了——这就是为什么本库 DP 系列按「约束类型」组织（相邻约束、背包约束、区间约束、树形约束），而不是按题目编号组织。

手动模拟与「环」变体的完整推演

用 [2,7,9,3,1] 手动模拟滚动数组，每一步的变量值列出来。初始：prev=0, curr=0。x=2：新 curr = max(0, 0+2) = 2（偷第一家）；prev, curr = 0, 2。x=7：新 curr = max(2, 0+7) = 7（不偷第一家、偷第二家更优）；prev=2, curr=7。x=9：新 curr = max(7, 2+9) = 11（偷第一家+第三家）；prev=7, curr=11。x=3：新 curr = max(11, 7+3) = 11（不偷第四家）；prev=11, curr=11。x=1：max(11, 11+1)=12（偷第五家）→ 答案 12 ✓。模拟中能看到的动态：「不偷」的选项如何被隐式继承（x=3 时「不偷」直接继承 11——dp[i-1] 的含义在变量里就是 curr）。环变体（LeetCode 213）的推演：[2,3,2] 围成环——首尾相邻，2 和 2 不能同偷。拆两个线性：情形 A（不偷最后一家）：[2,3] → rob=3；情形 B（不偷第一家）：[3,2] → rob=3；答案 max(3,3)=3。再验证一个：[1,2,3,1]（本库 rob 的测试用例）——情形 A：[1,2,3]→4（偷 1+3）；情形 B：[2,3,1]→3；答案 4 ✓ 与非环版一致（这家链条尾本来就不冲突）。环的拆法之所以正确：首尾相邻是唯一的额外约束，「必不偷首」或「必不偷尾」两个情形覆盖了所有最优解（最优解不可能同时偷首和尾）——把环形约束拆成两个线性问题的并集，是环上 DP 的通用手法。

「环」变体的完整推演与 UVa 式边界

环变体（LeetCode 213）的推演再补一个「全相同」边界：[2,2,2] 围成环——情形 A（不偷最后一家）：[2,2]→偷一家得 2；情形 B（不偷第一家）：[2,2]→得 2；答案 2（三个里偷一个——正确：环上任意两个都相邻）。再推 [2,2,2,2]：情形 A：[2,2,2]→4（偷 1+3 位）；情形 B：[2,2,2]→4；答案 4 ✓（隔一家偷两个）。环变体的一个实现细节：两个线性情形用「切片」实现时（rob(nums[:-1]) 与 rob(nums[1:])），单元素数组要特判（切片后为空——返回 nums[0]）。边界清单：空数组（0）、单元素（返回该元素）、双元素（返回较大者）、标准环。四个边界的最后一个共同点：环变体的所有边界，都是「线性 rob」边界与「切片」操作的组合——组合的正确性靠枚举验证，不靠灵光一现。

DP 的「转移依赖」可视化：一张两列状态机的运行图

滚动数组的三行核心代码，值得用「状态机运行图」可视化——它是理解所有「两变量滚动」DP 的通用图式。运行图（x 轴是房子序号，每个时刻两个状态变量的值）：i=0: (prev=0, curr=2)；i=1: (2, 7)；i=2: (7, 11)；i=3: (11, 11)；i=4: (11, 12)。图的读法：每个时刻「curr 变成 max(curr, prev+x)」——prev 是「上一轮的 curr 挪过来的」——两个变量像接力赛的两棒，每轮把 curr 的棒交给 prev，再算新 curr。运行图能回答的问题：转移方程的每项在图上的对应（curr 的继承 = 不偷；prev+x = 偷）；答案在哪个时刻定型（12 在最后一个房子才出现——早停就错）；为什么不能只用一个变量（偷 x 需要「x-2 时刻」的值——一个变量存不下两棒）。这个可视化的迁移价值：爬楼梯（同样的两棒）、斐波那契（无 max 的纯递推）、最大子数组和（curr 单变量的变体）——所有 O(1) 空间的线性 DP，都是「两棒接力」或「单棒竞速」的变体——画一次运行图，一族 DP 的空间优化全部通杀。

变形谱系：相邻约束 DP 的家族地图

打家劫舍是「相邻约束 DP」家族的起点，家族成员的谱系值得画全。原版（I）：线性数组、相邻不相容。II（环）：首尾相邻——拆双线性的通用手法（本篇正文）。III（树）：约束变成父子——树形 DP（本库《最大路径和》的骨架 + 状态向量：每个节点返回「偷/不偷」两状态）。删除与收益（LeetCode 740）：删 x 得 x 分且删掉所有 x+1 与 x-1——本质是「值域上的打家劫舍」（计数后按值域跑 rob——把问题转化成打家劫舍的视角转换是此题的全部难点）。带冷却的股票（LeetCode 309）的相邻面：卖出有一天冷冻——DP 状态多一维。家族地图的读法：约束（相邻/父子/值域邻接）与结构（线性/环/树）的二维组合，生成整个家族——学会「把新约束翻译成转移方程的变化」，一族题一起解决——这正是 DP 系列按约束类型组织的意义。

DP 代码的「读法训练」：三行代码的逐词解析

滚动数组的三行核心代码值得逐词解析——这是 DP 代码「读法训练」的最佳样本。第一行 prev, curr = curr, max(curr, prev + x)——右侧先全部求值再赋值（Python 的多变量赋值特性——右侧的 curr 和 prev 都是「上一轮」的值），这意味着赋值顺序无关紧要——这个特性在 C++ 等语言里不成立（需要临时变量保存旧值，否则 curr 的更新会污染 prev 的读取）；第二行 prev, curr = curr 之后的赋值——prev 接的是旧 curr（上一轮的最优），curr 接的是新计算（本轮的最优）——接力赛的换棒动作就在这一行；第三行循环结束 return curr——为什么不是 prev：prev 是「倒数第二轮」的最优，curr 才是「所有轮」的最优——边界感是读 DP 代码的核心素养。三行代码的逐词读法练熟了，一切「两变量滚动」的 DP（爬楼梯、斐波那契、最大子数组和）都有了通用的读法模板——读代码的速度，是刷题效率的隐形倍增器。

DP 代码的读法训练：三行代码的逐词解析

滚动数组的三行核心代码值得逐词解析——这是 DP 代码读法训练的最佳样本。第一行 prev, curr = curr, max(curr, prev + x)——右侧先全部求值再赋值（Python 的多变量赋值特性——右侧的 curr 和 prev 都是上一轮的值），这意味着赋值顺序无关紧要——这个特性在 C++ 等语言里不成立（需要临时变量保存旧值）。第二行 prev, curr 的赋值——prev 接的是旧 curr（上一轮的最优），curr 接的是新计算（本轮的最优）——接力赛的换棒动作就在这一行。第三行循环结束 return curr——为什么不是 prev：prev 是倒数第二轮的最优，curr 才是所有轮的最优——边界感是读 DP 代码的核心素养。三行代码的逐词读法练熟了，一切两变量滚动的 DP 都有了通用的读法模板——读代码的速度，是刷题效率的隐形倍增器。

小结

这篇收成四条：状态定义 dp[i] = 前 i 个房子的最大金额，「不偷第 i 个」自动被 dp[i-1] 覆盖，转移两项对应偷/不偷分支；转移只依赖前两项，滚动数组 O(1) 空间，三行代码是全部；本质是「不相邻约束下的最大子序列和」——打家劫舍 II（环）与 III（树）是同一约束在不同结构上的展开；DP 学习的方法论是按「约束类型」组织题目——学会「约束如何进入转移方程」，一族问题一起解决。DP 系列至此有了完整的入门线（爬楼梯 → 零钱兑换 → 编辑距离 → 本篇），下一篇《不同路径》把约束搬到网格上。

参考资料

• LeetCode 198. House Robber —— 题目与官方题解；LeetCode 213（II）、337（III）为系列续作
• 本库前篇：《LeetCode 70. 爬楼梯》《LeetCode 322. 零钱兑换》《LeetCode 72. 编辑距离》《LeetCode 124. 二叉树中的最大路径和》