最近刷 LeetCode Hot100 刷到第 68 题，正好是 198. 打家劫舍。这题在动态规划里算是最经典的“入门题中的入门题”，但真正能一次写对的人并不多。我见过不少面试者上来就写递归，写一半卡壳；也有人用贪心思路，反例一跑就翻车。这篇文章我会从题目场景讲起，把状态定义、转移方程、边界处理、滚动数组这些点一次说清楚，最后再分享几个我实际刷题时踩过的坑。

题目本身很直白：一排房屋，每间里藏着不同金额，小偷不能同时偷相邻的两间，否则触发警报。给定数组 nums，返回能偷到的最大金额。比如 [1,2,3,1]，最优是偷第1间和第3间，得到 1+3=4，千万不能偷 [1,2,1] 这种相邻组合。这篇文章适合刚开始接触动态规划、想把这类“选或不选”模型彻底搞懂的人，也适合刷题刷到瓶颈、想回头巩固状态转移基本功的老手。

1. 先搞清楚题目在考什么，再动手写代码

1.1 场景还原：一间房一间房地看问题

打家劫舍的场景其实是个典型的一维决策问题。数组下标就是房屋编号，值代表可偷金额。约束只有一条：不能偷相邻两个房间。注意这句话没有说“必须隔一间偷一次”，也没有说“不能连续跳过两间”。很多人一开始想歪，都是死在这句话上。

我习惯先把问题缩小：只看前 i 间房，问自己“如果只能在前 i 间里偷，最大收益是多少”。这样思考的好处是，不需要考虑后面的房间，问题被切成很多类似的小块。计算机科学里这叫“无后效性”——我关心的是前 i 间的结果，至于前 i-1 间到底怎么偷的，不需要知道细节，只知道它的最优值就够了。后面的状态只需要这个最优值参与计算。

举个反例来说明为什么不能拍脑袋：假设 nums = [2, 1, 1, 2]。如果采取“隔一间偷一次”的策略，可能偷第1间和第3间，得到 2+1=3；或者偷第2间和第4间，得到 1+2=3。但最优结果是偷第1间和第4间，2+2=4，中间空了第2、第3两间。这直接说明：约束是“不能相邻”，不是“必须间隔一”。后面我们写的状态转移方程，自然能覆盖这种情况。

1.2 为什么第一反应是动态规划，而不是贪心或双指针

刷题多了你会发现，凡是带“相邻”“不能同时选”这类限制的求最优问题，大概率要往动态规划想。原因很简单：你当前做决定会影响后面的选择。如果贪心地选当前收益最大的一间，可能把后面更高收益的组合堵死。双指针通常适合处理连续子段或有序数组的滑动窗口，这里没有那个结构。

动态规划能解决，是因为这个问题同时满足两个条件：一是重叠子问题，前 i 间的最优解会反复被后续计算用到；二是最优子结构，整体最优解可以由子问题的最优解推导出来。只要这两个条件成立，DP 就是最自然的工具。

也有一个很常见的错误思路：把所有偶数位或所有奇数位的和求出来，取较大值。这个想法在 [2,1,1,2] 上直接翻车，因为偶数位是 2+1=3，奇数位是 1+2=3，实际最优却是 4。原因还是“不能相邻”并不意味着“只能选同一奇偶下标”，它可以连续跳过两个房间。所以这一类题，老老实实做状态转移，别想太多捷径。

2. 从递归到状态定义：把“为什么”想透再写代码

2.1 先写“选或不选”的暴力递归

写 DP 之前，我强烈建议你先在纸上写一遍递归版本。它虽然效率差，但最能帮你理清转移关系。这里用从后往前看的思路：定义 dfs(i) 表示从第 i 间房开始（包含第 i 间）最多能偷多少。

面对第 i 间房，只有两个选择：

1. 不偷第 i 间，那么直接考虑下一间，结果就是 dfs(i+1)。
2. 偷第 i 间，因为不能偷相邻的 i+1 间，所以下一步从第 i+2 间继续，结果是 nums[i] + dfs(i+2)。

取两者较大值：

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

这个公式和信息论里“选或不选”的套路一模一样，只是后面跟着的状态不一样。边界条件也好写：如果 i 大于等于数组长度，一间房都没有，收益为 0；如果 i 是最后一间，直接返回 nums[i]，当然这个边界其实会被上面的递归自然处理。

用 [1,2,3,1] 手动走一遍：dfs(0) 对第0间，要么不偷看 dfs(1)，要么偷 1+dfs(2)。dfs(1) 要么不偷看 dfs(2)，要么偷 2+dfs(3)……你会发现这个递归树里 dfs(2)、dfs(3) 会被重复计算好几遍。这就是重叠子问题。所以暴力递归是 O(2^n)，n 稍大就跑不动，必须缓存中间结果。

2.2 缓存递归 vs 自底向上，到底选哪个

加了缓存的递归版本叫记忆化搜索，代码大体长这样：

from functools import lru_cache def rob(nums): n = len(nums) @lru_cache(None) def dfs(i): if i >= n: return 0 return max(dfs(i+1), nums[i] + dfs(i+2)) return dfs(0)

这个版本非常好懂，面试时可以当第一版。时间复杂度变成了 O(n)，因为每个 i 只算一次。但缺点也很明显：递归有函数调用栈开销，极端情况下 n 很大可能爆栈，而且 Python 的 lru_cache 虽然方便，但面试时你还要解释清楚缓存是怎么生效的。

所以我通常会在递归版本聊完后果断切到迭代版自底向上。思路反过来：先算最前面的小问题，再一步步推到大问题。这样空间可控，也不依赖递归深度。接下来就涉及核心的状态定义了。

2.3 状态定义和初始化，一举解决边界噩梦

这里给出一个我认为最好用的定义：dp[i] 表示前 i 间房屋（也就是 nums[0] 到 nums[i-1]）能偷到的最大金额。注意这个定义里的 i 是“前几间”，不是“第几个下标”，所以 dp[0]=0，表示一间都不偷。

在第 i 间房屋（下标 i-1）面前：

• 如果不偷它，前 i 间的收益就等于前 i-1 间的收益：dp[i-1]。
• 如果偷它，由于不能偷相邻的 i-2 间，所以收益等于 nums[i-1] + dp[i-2]。

于是转移方程：

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

这种定义的妙处在于：dp[0]=0，dp[1]=max(0, nums[0])，不用单独特判长度为 1 的情况，循环从 i=2 开始。你还可以在数组前面多开一个位置，让下标完全对齐。写出来就是：

def rob(nums): n = len(nums) dp = [0] * (n + 1) # 多开一位，dp[0]表示没有房间 if n >= 1: dp[1] = nums[0] for i in range(2, n + 1): dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) return dp[n]

这里 dp[n] 就是前 n 间房的最优解，也是整个数组的答案。我特别喜欢这个写法的原因是：它把“下标偏移”集中到了循环里的 nums[i-1]，剩下的全是对应关系，不容易混。

2.4 两种常见状态定义的对照，避免自己绕晕

刷题群里经常有人问：为什么我写的 dp[1] 有时候是 nums[0]，有时候又是 0？原因很简单，因为 dp[i] 的含义不一样。如果把 dp[i] 定义为“到下标 i 为止的最大收益”，那么 dp[0]=nums[0]，dp[1]=max(nums[0], nums[1])，循环从 i=2 开始，返回 dp[n-1]。

如果按照“前 i 间”来定义，dp[0] 对应 0，dp[1] 对应 nums[0]，返回 dp[n]。这两种写法都能 AC，但你在同一次提交里千万别混着用，否则就会出现差一位的错误。我的建议是：统一用“前 i 间”，因为它在处理空数组和单元素时更稳健，也更方便滚动数组版本的理解。

3. 代码落地：从完整 DP 到滚动数组优化

3.1 版本一：完整 dp 数组，适合在面试中解释

上面这段代码可以直接跑。我们再用 [1,2,3,1] 推演一遍：

• dp[0] = 0，dp[1] = 1
• i=2：dp[2] = max(dp[1], dp[0]+nums[1]) = max(1, 0+2)=2，表示前两间里最多偷 2。
• i=3：dp[3] = max(dp[2], dp[1]+nums[2]) = max(2, 1+3)=4，这里就是“偷第3间（3）加上第1间（1）”。
• i=4：dp[4] = max(dp[3], dp[2]+nums[3]) = max(4, 2+1)=4，答案为 4。

注意 i=3 这一步，dp[1]+nums[2] 实际表达的是“不偷第二间，偷第三间”；你也可以理解成从第三间往前数两间的最优收益是 dp[1]，正好是第1间。所以方程天然允许你跳过多间，这也是它能给出正确结果的原因。

复杂度上，O(n) 时间和 O(n) 空间。对于 LeetCode 的输入范围，这个版本完全能过。但如果你在面试中写到这一步，面试官十有八九会追问：空间能不能优化？

3.2 版本二：两个变量滚动数组，空间降到 O(1)

观察转移方程 dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])，你会发现计算当前第 i 个状态时，只需要前面两个状态 dp[i-1] 和 dp[i-2]，更早的数组状态再也用不到。那还存整个数组干嘛？直接用两个变量“滚动”过去。

我习惯把两个变量命名为 prev2 和 prev1，分别代表 dp[i-2] 和 dp[i-1]。每处理一个新房间 num，当前最优 cur 就是：

cur = max(prev1, prev2 + num)

然后用 prev2 = prev1，prev1 = cur，进入下一间。这里有一个非常容易错的地方：必须先更新 prev2 再更新 prev1，而且更新 prev2 时要使用旧的 prev1，不能直接用更新后的值。如果分开写，顺序写反就全错了。用 Python 的多重赋值可以一次搞定：

prev2, prev1 = prev1, cur

整体代码：

def rob(nums): prev2 = 0 prev1 = 0 for num in nums: cur = max(prev1, prev2 + num) prev2, prev1 = prev1, cur return prev1

为什么初始化都是 0？因为一开始还没有处理任何房间，dp[-1] 和 dp[0] 对应当前的前两间和前一间都不存在，设为 0 正好等价于“没有收益”。这个写法连空数组也不用特判，遍历结束后 prev1 就是答案，空数组返回 0。不过为了可读性，我建议还是加上 if not nums: return 0，让面试官一眼看懂边界处理。

3.3 面试官追加问题：环形房屋和树形房屋怎么改

打家劫舍这一系列很爱出变体。LeetCode 213 是环形街区，房子首尾相连。打破环的思路其实还是靠状态定义，但需要你把问题拆成两条不重叠的链：要么偷第一家，放弃最后一家；要么不偷第一家，可以考虑偷最后一家。分别跑一次原始线性 DP，取最大值。

LeetCode 337 是二叉树形的房屋布局，父子节点不能同时偷。这时候要做的是后序遍历，每个节点返回两个数：偷当前节点时的收益和不偷当前节点时的收益。父节点根据子节点的两种状态来组合，本质还是“选/不选”模型。等你把 198 彻底吃透，再刷 213 和 337 会轻松很多，因为核心都是同一个状态转移思想。

3.4 一个让我少写很多 if 的哨兵写法

如果你不想在 dp 数组版里单独处理 n=0、n=1，可以像下面这样给数组多开两个位置，让它天然带上两个 0：

def rob(nums): dp = [0] * (len(nums) + 2) for i in range(len(nums)): dp[i + 2] = max(dp[i + 1], dp[i] + nums[i]) return dp[-1]

这个写法看起来有点 trick，但实际很有用。它相当于把 dp[i] 和 dp[i+1] 预置成 0，然后从 nums[0] 开始一个一个往后面“累”最优值。循环结束后 dp 的最后一个位置就是结果。空数组返回 dp[-1]=0，单元素数组也能直接算对。我第一次看到这个写法时愣了半天，后来在代码里试过几次，发现面试时写出来既能秀一下对状态转移的熟练度，也能省掉大段的边界判断。

4. 刷题时最容易踩的坑，我全踩过

4.1 边界条件：空数组和只有一间房

很多人在 LeetCode 上提交后报错，原因就是长度短。用 dp 数组版本时，如果 n=0，dp[1] 会越界；如果 n=1，for 循环不执行，但 dp[1] 已经正确赋值，所以问题不大，前提是你写了 if 判断。我的习惯是开头三连：

if not nums: return 0 if len(nums) == 1: return nums[0]

有了这三个判断，后面可以放心写。滚动数组版本虽然不需要，但这三行能帮你和看代码的人快速确认边界，面试时加分。

4.2 错误思维：误以为必须“隔一间偷”

这一点我前面已经举过 [2,1,1,2] 的例子，但值得再说一次，因为它实在是高频错误。有人会把问题简化成“奇数下标和偶数下标”，然后比较哪个大，这种做法在大部分测试用例上可能碰巧正确，但一旦出现连续空两个房间更优的用例就翻车。还有人写成“每隔一个取”，同样不对。

你只要记住状态转移里的 nums[i-1] + dp[i-2] 里的 dp[i-2] 本身是“前 i-2 间的最优解”，它可能已经跳过了很多房间。所以在最终答案里，两个被偷的房间之间可以隔着任意多个房间，不一定正好一间。这个“理解”比代码本身更重要。

4.3 滚动数组更新顺序写反，越改越乱

我记得我第一次写滚动数组时是分开赋值：

prev2 = prev1 prev1 = max(prev1, prev2 + num)

结果怎么调都不对。原因是第二行里的 prev2 已经被更新成了旧的 prev1，不再代表 dp[i-2]。正确的顺序是先把旧 prev1 存到 prev2，再用旧的 prev2 和旧 prev1 计算当前 cur，最后把 cur 扔给 prev1。用 Python 多重赋值写最稳：

cur = max(prev1, prev2 + num) prev2, prev1 = prev1, cur

如果你习惯 Java/JavaScript，就先临时变量存 oldPrev = prev1，再分别更新。总之，先算，再挪，顺序别乱。

4.4 状态定义和下标偏移混在一起

使用 dp[i] 表示前 i 间房时，很多人会在循环里把 nums[i] 写成 nums[i-1]，结果提交报错；又有人把 dp 长度写 n，然后用 dp[i+1]，最后自己也绕晕。我建议要么统一用“前 i 间”定义，dp 开 n+1 长度；要么干脆用滚动数组，根本没有下标问题。如果你想兼容两种写法，可以做一个对照表：

表格的好处是，刷题多了以后你能根据题目要求快速选用，而不是每次现场推。

4.5 我常用的排查表，基本能解决 90% 的提交错误

遇到错误时，先别急着瞎改，按症状对号入座：

这张表是我自己刷题时总结的，现在每次写一维 DP 题，提交前都会默念一遍。

5. 复盘与串联：这类 DP 题以后怎么做到秒杀

5.1 四步法：以后遇到“相邻冲突”直接套

我后来刷了一堆类似题，总结出四步模板：

1. 判断是否满足两个条件：当前选择会影响后续选择 + 子问题之间有重复。满足就锁定 DP。
2. 定义状态。推荐用“前 i 个元素能获得的最优值”这类有偏移量的定义，天然包含空状态。
3. 写出“选/不选”两种分支对应的状态转移方程，再补边界。
4. 看 dp[i] 是否只依赖前两个状态，如果是，顺手优化成滚动数组。

这套模板在做 LeetCode 70 爬楼梯、53 最大子数组和、121 买卖股票的最佳时机时都管用。只不过爬楼梯的转移是 dp[i] = dp[i-1] + dp[i-2]，最大子数组和是 dp[i] = max(dp[i-1]+nums[i], nums[i])，买卖股票则变成了“持有/不持有”两种状态。核心都是先定义清楚状态，再写转移。

5.2 和 Hot100 里其他题目的关联：同一种味道

在 Hot100 里，动态规划题目不少，但 198 打家劫舍几乎是最适合做“母题”的。它和 213 打家劫舍 II 是一对，和 337 打家劫舍 III 是另一对，后两者的题解里都会引用 198 的状态转移。如果你做 198 时只背代码，后面做 213 大概率卡住；但如果你真的理解了“选/不选 + 重叠子问题”，后面两道题只是把线性数组换成环形或树形，状态定义需要跟着结构调一调，思路完全一样。

我自己刷题的习惯是把这类“一维线性 DP”整理成一个专题，每道题写在笔记里只列三点：状态定义、转移方程、边界条件。刷完 198 后再刷 213，你会发现 213 其实就是跑两遍 198，代码量翻倍但难度不翻倍。

5.3 一些面试小技巧和个人习惯

最后分享几个在面试和实际刷题中验证过的习惯。写代码前，先把输入规模想清楚：如果 n 很大，直接写出滚动数组版本，能少说很多优化步骤；如果面试官想看你思考过程，可以先写完整 dp 数组，讲明白后再压缩变量，这样显得逻辑清晰。

测试用例不要只用题目给的。我每次提交前都会手跑四个用例：空数组、单元素、[2,1,1,2] 这种连续空两间的最优，以及 [1,2,3,1] 这种标准用例。这四个能覆盖绝大多数边界和理解错误。

对了，还有一个经常被问的问题：“所有金额都是正数，能不能贪心？”答案是不能。相邻约束下的全局最优不是简单的局部最优，这题只要加一个 [3,2,2,3] 的例子就能验证：贪心可能导致偷 3+2 或 2+3，但最优是 3+3=6。所以老老实实 DP，别跟出题人赌直觉。

我自己二刷这题时，已经不需要再回忆状态定义了，看到“不能相邻”四个字，手指自动就开始写 prev2 和 prev1。但每次复盘我都会提醒自己：代码能跑通只是第一步，能解释清楚 dp[i-1] 和 dp[i-2]+nums[i-1] 分别代表什么，才是真的把题吃透。要是你刷完这题后也能在三十秒内讲清楚状态转移，那么 Hot100 后面那些动态规划题，你就算有个扎实的底子了。