刷LeetCode刷到“打家劫舍”这道题的朋友应该都体会过那种感觉题目读起来很简单一排房子相邻两间不能同时进求能偷到的最大金额。但真到了要写状态转移方程的时候脑子容易绕进去尤其是刚接触动态规划的同学经常卡在边界条件和dp数组的定义上。作为LeetCode热门100题里的经典动态规划入门题它几乎是面试高频题单里的标配也是后续打家劫舍II、打家劫舍III的基石周赛里偶尔还会出现它的变体。这篇文章就围绕这道题把动态规划的思路拆开揉碎从最朴素的递归想法一路推导到空间O(1)的滚动数组写法再用我实际刷题踩过的坑给你提个醒。适合正在刷题准备面试的读者也适合刚学动态规划、想搞懂“状态”到底是什么的初学者。1. 打家劫舍到底在问什么三个最容易被忽略的边界条件1.1 题面约束的本质相邻房间的互斥关系原题描述很直接你是一个小偷沿街有一排房屋每个房屋里有特定金额的现金不能偷相邻的两间房否则会触发报警问最多能偷多少。LeetCode第198题英文名叫House Robber。它和热词里常被刷到的LeetCode热门100题、题解、周赛430挂钩说明这题的出场率确实不低。很多人第一次看题第一反应是“隔一家偷一家”然后把数组分成奇数和偶数下标两个集合分别求和取大者。这个思路是错的我给你举反例nums [2, 7, 9, 3, 1] 奇数下标索引1、37 3 10 偶数下标索引0、2、42 9 1 12 奇偶取大是12但正确答案是12吗走一遍偷索引02和索引29和索引41总和12且不相邻没问题。但再试另一种组合偷索引02、索引29跳过索引3偷索引41这其实就是奇偶方案。可如果把索引17和索引33加进去就冲突了。真正的最优解是偷索引17和索引33加上索引41不行因为3和4相邻所以是7 3 10然后试试偷02、29不偷3偷41共12这个更优。等一下我重新手算一下这个例子的正确结果。数组[2, 7, 9, 3, 1]我们要选一个子序列不能选相邻元素求最大和。可选组合偷0、2、42 9 1 12偷0、211偷0、35偷0、43偷1、310偷1、48偷2、410偷0、2、4 12偷2单独 9偷1 7偷3 3偷4 1偷0、2不行和偷1冲突吗不0和2不相邻1和3不相邻但0和1相邻、2和3相邻。所以0、2、4合法12是解1、3合法10。 所以最大确实是12奇偶方案碰巧对了。这就是这个反例不够有力它恰好让奇偶方法也得到12。再构造一个反例[3, 2, 1]奇数下标索引1 2偶数下标索引0、2 314奇偶取大4但偷索引0和2不相邻吗索引0和2不相邻之间隔了索引1所以314也是对的。这个例子也不行。真正能拆穿奇偶法的例子是[2, 1, 1, 2]。奇数下标索引1、31 2 3偶数下标索引0、22 1 3奇偶取大3但最优解是偷索引02和索引32中间隔了1和2两个房间不相邻总和4。奇偶法在这里会漏掉最优解。这个例子说明“固定隔一个偷一个”是错误直觉因为最优解完全可能跳过两个或更多的房间只在你认为收益最大的地方下注。所以这道题不能用“按下标奇偶分组”的方式解必须考虑每个房子“偷还是不偷”的决策。1.2 空数组和单元素数组边界条件的魔鬼细节LeetCode的测试用例里nums为空、nums只有一个元素这两种情况一定会出现。很多新手在写动态规划时初始化dp数组长度为n然后写dp[1] nums[1]如果n等于1这一行直接数组越界。这也是为什么我在实际刷题时第一件事就是先把空数组和长度1的用例在草稿纸上过一遍。单元素数组的最好处理方式是在初始化时直接做判断n len(nums) if n 0: return 0 if n 1: return nums[0]这两行看起来啰嗦但对于后面所有递推代码的稳健性至关重要。而且LeetCode里这种输入很常见有时候题目会给[]这种极简用例如果你不在最前面兜住后面写再漂亮的转移方程也会在第一行就崩。1.3 状态定义要先于递推公式我一直觉得动态规划题能不能做出来一半以上取决于状态定义是否清晰。打家劫舍这题最常见的定义是dp[i]表示从第0间房子到第i间房子包含第i间这一段里能偷到的最大金额。有了这个定义递推关系就容易表达了对于第i间房子你有两个选择要么偷它要么不偷它。如果偷它因为它和第i-1间相邻所以第i-1间就不能偷此时总金额是dp[i-2] nums[i]如果不偷它那第i-1间是否被偷无所谓总金额就是dp[i-1]。取这两种选择的最大值就是dp[i]。这里有个细节要强调dp[i]并不是“在必须偷第i间的前提下”的最大值而是“考虑前i1间房子时”的最大值。我见过不少同学把状态定义成“偷到第i间房时的最大金额”然后递推时把dp[i]写成dp[i-2] nums[i]没有跟dp[i-1]做比较这样会漏掉大量更优的不偷方案。状态定义差一个字整个转移方程就彻底变味了。2. 从暴力递归到动态规划状态转移方程的推导全过程2.1 为什么暴力搜索会指数爆炸在动态规划被发明之前先想一下暴力解法长什么样。对于每间房子都有“偷”和“不偷”两个选择而且这两个选择还会影响后面的房子。如果n是10可能存在2的10次方种方案n是50方案数就是天文数字。暴力递归的做法会重复计算大量子问题比如你在递归树的左侧计算了rob(0, 4)右侧可能又要计算一次rob(0, 4)这种重叠子问题是动态规划可以优化的基础。打家劫舍这题有个特别适合人类直觉的递归写法def rob_rec(nums, i): if i 0: return 0 return max(rob_rec(nums, i - 1), rob_rec(nums, i - 2) nums[i])这个递归的逻辑是站在第i间房子门前要么不进去去考虑前i-1间要么进去偷但前提是第i-1间被跳过所以回到第i-2间。边界是i小于0时返回0。这其实就是dp[i] max(dp[i-1], dp[i-2] nums[i])的递归形态。很多教学材料直接给你递推公式却不说它是怎么来的。我建议时间充裕的读者先把这个递归函数在纸上跑一遍[2, 7, 9, 3, 1]画一棵递归树你会很直观地看到同一个子问题被反复计算多次。比如rob(3)被rob(4)和rob(3)的上级各自调用整个树的节点数接近指数级。这时候再把递归树中相同节点缓存结果就是带备忘录的递归进一步改成从底向上填表就是标准的动态规划。2.2 从递归到填表自底向上的完整手算把递归改成迭代最重要的转变是思考方向递归是从第n-1间往前推动态规划是从第0间往后推。我们要先初始化前两个状态然后依次计算后面的所有状态。按照dp[i]的定义初始化应该是dp[0] nums[0]只有一间房时不偷白不偷最大收益就是它本身。dp[1] max(nums[0], nums[1])有两间房时必须在第0间和第1间里二选一因为相邻不能同时偷。然后从i2开始遍历到n-1执行状态转移dp[i] max(dp[i-1], dp[i-2] nums[i])我拿[2, 7, 9, 3, 1]实际走一遍你感受一下填表的过程inums[i]dp[i-2] nums[i]dp[i-1]dp[i]02无无217无27292911711337310111141111121112最终dp[4]12对应正是偷第0、2、4间房总金额12。注意i3的时候dp[3]是11而不是10说明最优策略在第三间房时选择了不偷第3间维持了前两间的最优状态。这种“当前最优状态可能在某个位置选择跳过”的特性恰恰是上一节里奇偶分组法会漏解的根本原因。2.3 为什么最终答案就是dp[n-1]这是很多初学者最后一步会犯嘀咕的地方题目要求整条街的最大收益为什么就是最后一个状态呢因为dp[i]的定义是“考虑前i1间房时的最大金额”当i遍历到n-1时它已经考虑了所有的房间所以它的值就是全局最优解。这里要区分一个概念dp[n-1]和dp[n-2]在实际中可能相等比如刚才例子里dp[3]11、dp[4]12不相等但如果你遇到[2, 1, 1, 2]dp[2]max(dp[1], dp[0]1)max(2,3)3dp[3]max(dp[2], dp[1]2)max(3,4)4。最后一间房被偷了。有时候最后一间房不被偷dp[n-1]就等于dp[n-2]。这没关系你只需要返回dp[n-1]它就是全局最大因为如果不偷最后一间能拿到更大收益dp[n-1]会自动取到dp[n-2]的值。我之前见过有人非要返回max(dp)这样也能过但没必要而且会让代码显得不干净。在面试场景里面试官问“返回值为什么是这个”你能解释清楚“dp[n-1]已经是考虑完全部房屋的最优值”这比“我直接取了数组最大值”要好得多。3. 空间复杂度从O(n)降到O(1)滚动数组的原理与坑3.1 转移方程为什么只依赖前两个状态观察dp[i] max(dp[i-1], dp[i-2] nums[i])你会发现dp[i]的计算只用到dp[i-1]和dp[i-2]再往前dp[i-3]、dp[i-4]之类完全没有参与。这意味着用一整个dp数组来装所有历史状态是浪费的——我们只需要记住最近的两个状态就可以一路把答案算到底。这就是滚动数组滑动状态的核心思想把动态规划数组压缩成有限个变量。打个生活化的比方你走台阶每次只看得到前两级台阶上放着什么不需要把走过的所有台阶都拍下照片放在口袋里。只需要记住“上一级的结果”和“上上一级的结果”走到第i级时用这两个值推导当前然后把“上一级”降级为“上上一级”把“当前”变成新的“上一级”继续往前走。3.2 两个变量加一个临时变量的经典写法一个最常见的滚动数组实现是这样的def rob(nums): n len(nums) if n 0: return 0 if n 1: return nums[0] prev2 nums[0] # dp[i-2]的初始值 prev1 max(nums[0], nums[1]) # dp[i-1]的初始值 for i in range(2, n): cur max(prev1, prev2 nums[i]) prev2 prev1 prev1 cur return prev1这里prev2对应dp[i-2]prev1对应dp[i-1]。循环开始时i2所以prev2nums[0]即dp[0]prev1max(nums[0], nums[1])即dp[1]正好是转移方程需要的前两个状态。每轮循环算出cur后把prev1赋值给prev2把cur赋值给prev1这样就完成了状态滚动。这是最稳妥的写法。你可能见过网上有人用三个变量a、b、c来做同样的滚动还有人用Python的并行赋值一行搞定prev2, prev1 nums[0], max(nums[0], nums[1]) for i in range(2, n): prev2, prev1 prev1, max(prev1, prev2 nums[i]) return prev1并行赋值在Python里是“等号右边先整体求值再统一赋值”所以不会出现中间变量被覆盖的问题能少写一行tmp。但我个人建议在面试手写代码时用带临时变量的版本因为它在任何语言里都可移植而且逻辑对面试官来说更透明。用并行赋值虽然优雅但如果面试官用的是C或Java你得临时改成int temp b; b max(...); a temp;思路还得重新转一圈。3.3 滚动数组最经典的翻车现场更新顺序写反我曾经在给朋友review代码时看到过这样一段prev2 nums[0] prev1 max(nums[0], nums[1]) for i in range(2, n): prev2 prev1 prev1 max(prev2, prev2 nums[i]) # 这里的prev2已经被覆盖了 return prev1看出来了吗在计算max(prev2, prev2 nums[i])之前prev2已经被prev1覆盖了。于是prev2 nums[i]变成了prev1 nums[i]递推变成了dp[i] max(dp[i-1], dp[i-1] nums[i])相当于忽略“跳过前一个房间偷当前房间”的收益加成。这个错误极难靠肉眼察觉因为大部分测试用例都能算出看起来差不多的结果只有在特定数组上才会差个几块钱。我在刷题时吃过这个亏后面养成了一个习惯凡是滚动数组更新都会先把旧值存进临时变量再用临时变量参与所有计算更新顺序严格遵循“先求值再滚动”。3.4 什么时候必须保留完整dp数组滚动数组省空间但也丢掉了“历史最优路径”。如果题目稍微改一下要求你输出偷的是哪几间房或者要求你解释dp在哪个位置发生了“不偷”的决策滚动数组就无能为力了。LeetCode原题只需要返回金额用滚动数组没问题但如果面试官现场加问“能不能把偷的房间序号也输出”你就要立刻切回完整dp数组方案并反推决策# 完整dp数组反推路径 dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i-1], dp[i-2] nums[i]) # 从后往前反推选了哪些房间 result [] i n - 1 while i 0: if i 1 and dp[i] dp[i-1]: i - 1 else: result.append(i) i - 2 result.reverse()这个小扩展在面试中经常被问到建议你提前练一下。它的逻辑也不复杂如果dp[i]等于dp[i-1]说明第i间没有被偷往后退一格否则说明偷了第i间把i加入结果然后跨过第i-1间直接跳到i-2继续判断。4. 完整AC代码与真实调试心得这题在面试和笔试里的隐藏考点4.1 一份可以直接用的标准实现把前面所有要点合并成一份完整代码我平时在LeetCode提交的就是这个版本from typing import List class Solution: def rob(self, nums: List[int]) - int: n len(nums) if n 0: return 0 if n 1: return nums[0] prev2 nums[0] prev1 max(nums[0], nums[1]) for i in range(2, n): cur max(prev1, prev2 nums[i]) prev2 prev1 prev1 cur return prev1这是我在LeetCode上最终定稿的样子。类型注解List[int]可有可无但写上之后对IDE的自动补全更友好也更容易让面试官觉得你代码习惯好。时间复杂度O(n)只遍历了一遍数组空间复杂度O(1)常数个额外变量。4.2 我每次都要跑的一组测试用例调试动态规划题最怕的就是“测试用例太温和错误代码也能跑出正确答案”。所以我给自己列了一个标准清单每次写完打家劫舍都会先拿这组用例过一遍输入期望输出备注[]0空数组兜底[5]5单元素边界[2, 1]2两元素取最大[1, 2, 3, 1]4经典用例偷索引0和2[2, 1, 1, 2]4拆穿“奇偶分组”错误解法的用例[2, 7, 9, 3, 1]12LeetCode原题示例[1, 3, 1, 3, 100]103用来验证长距离跳转最优解是偷1、3、4吗不对偷1、3后不能偷4所以33偷0、2、411100102偷1、43100103。这个用例能让你确认跳过两个房间的选择特别注意[2, 1, 1, 2]这个用例。如果你写的是“把数组拆成奇偶下标算和再比较”的思路它会直接输出3但正确答案是4。很多人在网上发题解时自己用的也是错的奇偶思路而不自知原因就是他们没跑过这个反例。这种测试用例本身就是最好的学习材料能帮你验证状态转移方程是不是真的考虑了所有决策。4.3 初始化的两种常见写法以及各自容易踩的坑我在网上看过很多题解初始化方式五花八门但归结起来主要有两种。第一种是上面代码里的prev2 nums[0], prev1 max(nums[0], nums[1])这种写法的好处是跟dp数组的初始化一一对应逻辑直白不容易算错i的起始位置。第二种是造一个长度为n1的dp数组约定dp[0] 0表示没有房子时收益为0dp[1] nums[0]然后从i2开始递推递推公式里的下标要整体偏移一位dp [0] * (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[0]天然就是0缺点是下标偏移容易看花眼。我自己两种都写过结论是只要你能保证循环体内所有的nums下标都做了减一处理第二种写法就能work但如果你在写转移方程时复制粘贴漏了一个-1调试起来会非常痛苦。给新手读者的建议是选第一种把下标和含义一一对应不容易出错。4.4 面试现场被追问的表现建议打家劫舍在面试里出现时很少有人直接扔你一道裸题。面试官常见的加问有为什么不能用贪心为什么奇数下标之和不是答案你能把它改成输出路径吗你能否把空间压缩到O(1)关于贪心我见过有人说“每次都看下下家如果下下家更大就跳过当前”这类局部最优策略很容易举出反例。比如[2, 1, 1, 2]站在索引0看下下家是索引2的1小于当前的2于是偷0然后到索引1下下家是索引3的2大于1跳过1到索引3直接偷2这样得到的是224居然对了。再换[3, 2, 1, 3]索引0看下下家1偷3索引1看下下家3大于2跳过索引3偷3得到6。但正确解法是索引0和索引2314或者索引1和索引3235都不是6。等等索引0的3和索引3的3不相邻中间隔了2和1两个房间应该是6这个反例又不对。我再认真找一个贪心失效的例子[5, 3, 4, 11, 2]贪心看当前和下下家索引0的5大于下下家4偷5索引1的3小于下下家11跳过索引2的4小于下下家2吗不大于所以偷4索引3的11大于下下家2偷11索引4的2最后偷但索引3偷了索引4不能偷。结果541120不对4和11之间隔了索引3索引2偷了4索引3的11可以偷因为不相邻结果541120。但最优解是索引1和索引331114或者索引0、索引2、索引454211都没到20。贪心得到了20比最优还高说明贪心选的序列可能不合法——等等检查一下贪心第一步偷索引0那索引1不能偷第二步看索引1的3下下家索引3的1111大跳过1第三步看索引2的4下下家索引4的24大偷2第四步索引3被跳过贪心看索引3是因为之前跳过了这里贪心算法没有统一的明确定义说不清楚。所以在面试里讨论贪心更稳妥的切入点是直接说明这题本质上是一个二维决策问题每个房子选与不选会影响相邻选项贪心无法保证全局最优而动态规划通过记录每个前缀的最优解天然覆盖了所有合法方案。你不需要去构造复杂反例只需要指出“贪心的局部最优判断无法感知全局的收益分布”然后补一句“如果你愿意我可以现场构造一个反例”这一般就够了。真正的关键还是把动态规划的状态定义和转移逻辑讲清楚。4.5 调试时最值得打印的信息如果你在本地调试这类题不要一上来就print整个dp数组。我调试滚动数组版本时通常只打印每次循环的i、prev2、prev1和cur四个值。这样能快速定位是更新顺序错了还是初始值错了。经典错误之一是prev1的初始化写成nums[1]导致当数组长度为2、且第二个元素小于第一个元素时答案直接算错。打印初始化之后的prev2、prev1立刻就能发现问题。5. 打家劫舍系列怎么学从线性到环形再到树形5.1 打家劫舍II环形数组怎么拆原题是一排房子打家劫舍IILeetCode 213变成了一圈房子第0间和第n-1间相邻。这样你首尾不能同时抢思路就变成了“分情况讨论”要么不抢第0间把第1间到第n-1间当作线性数组来求要么不抢第n-1间把第0间到第n-2间当作线性数组来求。两种结果取最大值即可。这里有个细节如果你把仅有一间房的情况单独处理两个子数组就分别是nums[1:]和nums[:-1]都能复用同一个一维打家劫舍函数。现实中环形数据结构不少见这种“拆环为链”的思路在很多题目里都能复用所以很值得顺便学一学。5.2 打家劫舍III树形DP与状态返回值的妙用再进阶一步打家劫舍IIILeetCode 337把数组换成了二叉树。房子沿二叉树分布不能同时抢直接相邻的两个节点父子节点。这时线性dp的数组递推不再适用需要换成树形动态规划。常规做法是定义递归函数dfs(node)返回两个值rob表示抢当前节点能得到的最大金额not_rob表示不抢当前节点能得到的最大金额。转移关系是抢当前节点时左右孩子都不能抢rob node.val left.not_rob right.not_rob不抢当前节点时左右孩子各自取最大not_rob max(left.rob, left.not_rob) max(right.rob, right.not_rob)这个做法的核心思路跟线性版完全同源都是“当前节点抢不抢”的决策只不过把一维数组的上下文变成了树的后序遍历。很多人在学完198之后直接去啃337会被递归和双返回值搞晕但如果你先把线性版的状态定义吃透再看树形版本质就是同一套思维在不同数据结构上的映射。5.3 三道题放在一起的复习路径我比较推荐的学习节奏是把198、213、337看作一个系列逐层递进。先确保自己能十分钟内默写出线性版滚动数组代码再尝试把线性版抽成一个工具函数去跑213的两个子数组最后再碰337的树形DP。一道题单独做可能印象不深但三道题放在一起刷你会很明显地看到从数组到环形数组到二叉树变化的只是数据的排列方式不变的永远是“选或不选并保证不选相邻冲突”的决策框架。有一件事我每次刷动态规划这方面的题都想强调状态定义里的“考虑前i个”这个措辞值得反复咀嚼。它意味着dp[i]并不强制要求第i个元素被选中它只是一个前缀范围内的最优解容器。很多玄学错误说到底都是把“考虑”理解成了“必须选”。想通了这一点打家劫舍系列的一道题和后面的很多变体都会顺畅很多。你在纸上把[2, 1, 1, 2]的dp数组手算一遍再对比滚动数组每轮变量的变化就会发现动态规划并没有那么玄它只是在用表格记录“每一步做选择时前面已经算好的最优答案”罢了。