最近刷 LeetCode Hot100 刷到第 68 题正好是 198. 打家劫舍。这题在动态规划里算是最经典的“入门题中的入门题”但真正能一次写对的人并不多。我见过不少面试者上来就写递归写一半卡壳也有人用贪心思路反例一跑就翻车。这篇文章我会从题目场景讲起把状态定义、转移方程、边界处理、滚动数组这些点一次说清楚最后再分享几个我实际刷题时踩过的坑。题目本身很直白一排房屋每间里藏着不同金额小偷不能同时偷相邻的两间否则触发警报。给定数组 nums返回能偷到的最大金额。比如 [1,2,3,1]最优是偷第1间和第3间得到 134千万不能偷 [1,2,1] 这种相邻组合。这篇文章适合刚开始接触动态规划、想把这类“选或不选”模型彻底搞懂的人也适合刷题刷到瓶颈、想回头巩固状态转移基本功的老手。1. 先搞清楚题目在考什么再动手写代码1.1 场景还原一间房一间房地看问题打家劫舍的场景其实是个典型的一维决策问题。数组下标就是房屋编号值代表可偷金额。约束只有一条不能偷相邻两个房间。注意这句话没有说“必须隔一间偷一次”也没有说“不能连续跳过两间”。很多人一开始想歪都是死在这句话上。我习惯先把问题缩小只看前 i 间房问自己“如果只能在前 i 间里偷最大收益是多少”。这样思考的好处是不需要考虑后面的房间问题被切成很多类似的小块。计算机科学里这叫“无后效性”——我关心的是前 i 间的结果至于前 i-1 间到底怎么偷的不需要知道细节只知道它的最优值就够了。后面的状态只需要这个最优值参与计算。举个反例来说明为什么不能拍脑袋假设 nums [2, 1, 1, 2]。如果采取“隔一间偷一次”的策略可能偷第1间和第3间得到 213或者偷第2间和第4间得到 123。但最优结果是偷第1间和第4间224中间空了第2、第3两间。这直接说明约束是“不能相邻”不是“必须间隔一”。后面我们写的状态转移方程自然能覆盖这种情况。1.2 为什么第一反应是动态规划而不是贪心或双指针刷题多了你会发现凡是带“相邻”“不能同时选”这类限制的求最优问题大概率要往动态规划想。原因很简单你当前做决定会影响后面的选择。如果贪心地选当前收益最大的一间可能把后面更高收益的组合堵死。双指针通常适合处理连续子段或有序数组的滑动窗口这里没有那个结构。动态规划能解决是因为这个问题同时满足两个条件一是重叠子问题前 i 间的最优解会反复被后续计算用到二是最优子结构整体最优解可以由子问题的最优解推导出来。只要这两个条件成立DP 就是最自然的工具。也有一个很常见的错误思路把所有偶数位或所有奇数位的和求出来取较大值。这个想法在 [2,1,1,2] 上直接翻车因为偶数位是 213奇数位是 123实际最优却是 4。原因还是“不能相邻”并不意味着“只能选同一奇偶下标”它可以连续跳过两个房间。所以这一类题老老实实做状态转移别想太多捷径。2. 从递归到状态定义把“为什么”想透再写代码2.1 先写“选或不选”的暴力递归写 DP 之前我强烈建议你先在纸上写一遍递归版本。它虽然效率差但最能帮你理清转移关系。这里用从后往前看的思路定义 dfs(i) 表示从第 i 间房开始包含第 i 间最多能偷多少。面对第 i 间房只有两个选择不偷第 i 间那么直接考虑下一间结果就是 dfs(i1)。偷第 i 间因为不能偷相邻的 i1 间所以下一步从第 i2 间继续结果是 nums[i] dfs(i2)。取两者较大值dfs(i) max(dfs(i1), nums[i] dfs(i2))这个公式和信息论里“选或不选”的套路一模一样只是后面跟着的状态不一样。边界条件也好写如果 i 大于等于数组长度一间房都没有收益为 0如果 i 是最后一间直接返回 nums[i]当然这个边界其实会被上面的递归自然处理。用 [1,2,3,1] 手动走一遍dfs(0) 对第0间要么不偷看 dfs(1)要么偷 1dfs(2)。dfs(1) 要么不偷看 dfs(2)要么偷 2dfs(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(i1), nums[i] dfs(i2)) 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]0dp[1]max(0, nums[0])不用单独特判长度为 1 的情况循环从 i2 开始。你还可以在数组前面多开一个位置让下标完全对齐。写出来就是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])循环从 i2 开始返回 dp[n-1]。如果按照“前 i 间”来定义dp[0] 对应 0dp[1] 对应 nums[0]返回 dp[n]。这两种写法都能 AC但你在同一次提交里千万别混着用否则就会出现差一位的错误。我的建议是统一用“前 i 间”因为它在处理空数组和单元素时更稳健也更方便滚动数组版本的理解。3. 代码落地从完整 DP 到滚动数组优化3.1 版本一完整 dp 数组适合在面试中解释上面这段代码可以直接跑。我们再用 [1,2,3,1] 推演一遍dp[0] 0dp[1] 1i2dp[2] max(dp[1], dp[0]nums[1]) max(1, 02)2表示前两间里最多偷 2。i3dp[3] max(dp[2], dp[1]nums[2]) max(2, 13)4这里就是“偷第3间3加上第1间1”。i4dp[4] max(dp[3], dp[2]nums[3]) max(4, 21)4答案为 4。注意 i3 这一步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 prev1prev1 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 数组版里单独处理 n0、n1可以像下面这样给数组多开两个位置让它天然带上两个 0def 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[i1] 预置成 0然后从 nums[0] 开始一个一个往后面“累”最优值。循环结束后 dp 的最后一个位置就是结果。空数组返回 dp[-1]0单元素数组也能直接算对。我第一次看到这个写法时愣了半天后来在代码里试过几次发现面试时写出来既能秀一下对状态转移的熟练度也能省掉大段的边界判断。4. 刷题时最容易踩的坑我全踩过4.1 边界条件空数组和只有一间房很多人在 LeetCode 上提交后报错原因就是长度短。用 dp 数组版本时如果 n0dp[1] 会越界如果 n1for 循环不执行但 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[i1]最后自己也绕晕。我建议要么统一用“前 i 间”定义dp 开 n1 长度要么干脆用滚动数组根本没有下标问题。如果你想兼容两种写法可以做一个对照表写法dp[i]含义循环范围转移方程返回前i间dp长度n1前i间最大收益1..ndp[i]max(dp[i-1],dp[i-2]nums[i-1])dp[n]第i下标dp长度n到下标i为止最大收益2..n-1dp[i]max(dp[i-1],dp[i-2]nums[i])dp[n-1]表格的好处是刷题多了以后你能根据题目要求快速选用而不是每次现场推。4.5 我常用的排查表基本能解决 90% 的提交错误遇到错误时先别急着瞎改按症状对号入座症状可能原因处理方法数组越界 IndexError没处理空数组或 dp 长度不够开头补 if not numsdp 长度设 n1 或 n2小用例能过大用例超时写了纯递归没用缓存或迭代改成自底向上 DP或者加 lru_cache[2,1,1,2] 结果不对误用“隔一个偷”或奇偶下标取和回到状态转移方程用 dp[i-2]nums[i-1]滚动数组结果比预期小更新顺序写反先算 cur再同时更新 prev2、prev1结果总差 1 或漏掉最后一家循环范围没覆盖 n或下标偏移搞混统一用“前 i 间”定义循环写 range(1, n1)这张表是我自己刷题时总结的现在每次写一维 DP 题提交前都会默念一遍。5. 复盘与串联这类 DP 题以后怎么做到秒杀5.1 四步法以后遇到“相邻冲突”直接套我后来刷了一堆类似题总结出四步模板判断是否满足两个条件当前选择会影响后续选择 子问题之间有重复。满足就锁定 DP。定义状态。推荐用“前 i 个元素能获得的最优值”这类有偏移量的定义天然包含空状态。写出“选/不选”两种分支对应的状态转移方程再补边界。看 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] 的例子就能验证贪心可能导致偷 32 或 23但最优是 336。所以老老实实 DP别跟出题人赌直觉。我自己二刷这题时已经不需要再回忆状态定义了看到“不能相邻”四个字手指自动就开始写 prev2 和 prev1。但每次复盘我都会提醒自己代码能跑通只是第一步能解释清楚 dp[i-1] 和 dp[i-2]nums[i-1] 分别代表什么才是真的把题吃透。要是你刷完这题后也能在三十秒内讲清楚状态转移那么 Hot100 后面那些动态规划题你就算有个扎实的底子了。