第一次在LeetCode上刷到“打家劫舍”这个题名的时候我以为是个脑筋急转弯一排房子、现金、不能惊动邻居怎么看都像情景剧。直到真正点进去才发现这道题是把动态规划最核心的“状态定义 状态转移”讲得最透彻的题目之一。LeetCode打家劫舍系列一共有三兄弟198线性数组版、213环形街区版、337二叉树版常年霸榜热门100题是面试和刷题圈子里绕不开的经典套路。这个系列最值钱的地方不在于题目本身有多难而在于它用递进的难度带你走完了一整条动态规划的主线一维数组上的线性DP、环形数组的拆环技巧、再到树上树形DP。学会这套题后面再去碰股票买卖、背包问题、编辑距离这类经典DP你会发现自己有了一个清晰的分析框架。这篇文章我从头到尾把三道题拆开揉碎把每一步推导、每一个边界条件、每一个面试官爱追问的细节都写了看完可以直接照着思路复现也能顺手应付面试里的变体。1. 先搞清楚这套题到底在考什么1.1 一道题带出动态规划的核心脉络很多人刷动态规划的时候最大的困惑是看题解能看懂自己写就卡壳。问题往往出在“状态是怎么想出来的”这一环。打家劫舍系列的妙处就是它的状态几乎给人“送分”的感觉——每个房子只有两种决策偷或者不偷。但恰恰是这个看似简单的决策把动态规划的推导逻辑完整走了一遍。先看198题的描述一排房子每个房子里有不同数量的现金你不能偷相邻的两家问能偷到的最大金额。这个约束条件“不能偷相邻”就是整道题的灵魂。它意味着当你站在第i个房子面前做决定时你的选择不仅要考虑当前房子的价值还要被上一个房子的选择约束。这种“当前决策受过去状态影响”的结构天然就是动态规划的狩猎场。我经常用一句话帮助初学者建立直觉每一步都面临“偷”或“不偷”的分岔路每一种选择都会改变后面路线的可能性你要找的是一条收益最大的完整路线。暴力枚举所有路线当然能做但复杂度是指数级的因为每个房子都会把局面分裂成两个分支。动态规划的价值就是发现这些分支之间存在着大量的重叠子问题——第i个房子的状态只取决于前两个房子的结果跟更早的历史毫无关系。把这个“无后效性”看穿了题目就算破了一半。这个系列在LeetCode上被归为动态规划入门必刷清单属实名副其实。它不涉及区间DP、状态压缩、数位DP这些进阶技巧纯粹靠最基本的“状态定义—转移方程—边界条件—遍历顺序”四步走就能解非常适合作为学习DP的“四步走样板间”。1.2 三道题的难度阶梯与面试价值把三兄弟放在一起看完全是导演编排好的进阶路线题号结构形式核心技巧时间复杂度空间复杂度198 打家劫舍一维数组线性DP 滚动变量O(n)O(1)213 打家劫舍II环形数组拆环变线性O(n)O(1)337 打家劫舍III二叉树树形DP / 后序遍历O(n)O(树高)198题教会你最朴素的DP推导213题在198的基础上多了“首尾相连”这个限制考察你能否把环破开转成已经会做的线性问题337题则完全换了一个数据结构把数组换成了树迫使你把“顺序遍历”的思路升级成“后序遍历”。每一道都是上一道的延伸又不是简单的套壳这种递进关系在LeetCode题库里相当少见所以它才被无数面试官青睐。从面试角度讲打家劫舍系列是高频中的高频。尤其是198题属于那种“只要说自己在刷题就必须会”的题目。213和337则常常作为追问出现你说你做过198那房子围成环还会吗那房子变成一棵二叉树呢我在几次模拟面试里就遇到过面试官顺着这个系列一路问下去从198问到337再问到“如果房子排成了一个二维网格呢”。这套递进恰恰是考察候选人DP功底的好手段。把这三道吃透你等于从线性DP到树形DP都有了一个稳固的锚点后面学任何复杂DP都心里有底。2. 打家劫舍I一维数组上的状态转移2.1 状态设计与转移方程的推导逻辑打家劫舍ILeetCode 198是整套题的地基。拿到题目第一件事不是写代码而是想清楚“我的dp数组每个位置代表什么意思”。很多新手会下意识定义成“dp[i]表示偷到第i个房子时当前房子偷不偷带来的收益”结果把状态弄成了两个变量还纠结怎么互相转移。实际上这道题有一个更干净的定义dp[i]表示从第0个房子到第i个房子这段范围内能偷到的最大金额。这个定义里隐含着“我不关心第i个房子到底偷没偷我只关心这段范围的最优结果”。这样定义的好处是转移方程可以直接写出来dp[i] max(dp[i-1], dp[i-2] nums[i])拆开看这个方程它的逻辑其实是对“第i个房子偷不偷”的两种决策取最优如果第i个房子不偷那么第i-1个房子可以自由决策结果就是dp[i-1]。如果第i个房子要偷那么第i-1个房子绝对不能偷相邻约束所以只能从第i-2个房子的最优结果基础上加上nums[i]。这个推导就是我们常说的“状态转移方程”。你可能会问为什么dp[i-1]里不区分第i-1个房子到底偷没偷因为dp[i-1]已经是前i个房子能取得的最大值至于i-1偷没偷那是这个最大值内部的事情。这种“用子问题的最优解去构造更大范围最优解”的思想就是动态规划区别于贪心和暴力的关键。边界条件也需要单独处理。当数组长度为0时直接返回0长度为1时只能偷这一家返回nums[0]长度大于等于2时从第2个位置开始套转移方程。先初始化dp[0]nums[0]dp[1]max(nums[0], nums[1])因为前两个房子里你只能选金额更大的那家。2.2 用示例一步步推演dp全过程光看方程容易飘亲手推一遍样例比什么都管用。就拿LeetCode官方示例来走nums [2, 7, 9, 3, 1]。先初始化dp[0] 2因为只有一间房子不偷白不偷。dp[1] max(2, 7) 7前两间房不能同时偷选钱多的那间。然后从i2开始递推i2nums[2]9。dp[2] max(dp[1], dp[0] 9) max(7, 2 9) 11。这表示前3间房子最多能偷11路线是偷第0间和第2间。i3nums[3]3。dp[3] max(dp[2], dp[1] 3) max(11, 7 3) 11。注意这里dp[1]310说明“偷第1间和第3间”的方案不如“偷第0间和第2间”的11于是最优路线不变。i4nums[4]1。dp[4] max(dp[3], dp[2] 1) max(11, 11 1) 12。到这里答案就是12路线是偷第0间、第2间和第4间。走完一遍你就会发现dp数组每个值都是全局最优的一个局部快照而且它不需要知道之前具体走了哪条路线。这就是“无后效性”的直观表现。我在纸上推演的时候习惯把dp数组一行行写出来看着数字递推增长比盯着代码空想要踏实得多。2.3 空间优化到O(1)的滚动变量写法上面用dp数组的做法空间复杂度是O(n)。但注意转移方程里dp[i]只依赖dp[i-1]和dp[i-2]这意味着更早的dp[0]、dp[1]在使用之后就再无价值。于是我们可以用两个变量滚动向前把空间压到O(1)。LeetCode上这道题剑指offer版本和面试官都特别喜欢追问这个优化。直接看完整代码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] # 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这段代码里的滚动更新本质上就是在模拟dp数组的滑动窗口。prev2永远保存着dp[i-2]的值prev1保存着dp[i-1]的值每次算完当前cur之后整体往前挪一位。这个写法在股票买卖、斐波那契数列里也是同一个套路属于DP空间优化的“万金油”。另外提一个LeetCode上的小坑如果直接在本地跑需要from typing import List这行导入否则类型注解List[int]会报错。在网站上刷题时平台会自动处理这个但本地验证代码时就要自己加上。3. 打家劫舍II环形数组的拆环解题法3.1 为什么环形会让题目难度上升打家劫舍IILeetCode 213把第一题的线性结构升级成了环形结构所有房子围成一个圈第0间和第n-1间成了邻居。这意味着“不能偷相邻两家”的约束现在多了一条线上没有的规则——首尾也不能同时偷。这个变化直接把198题的dp定义推翻了一半。如果继续套用dp[i]表示“前i个房子的最大收益”你会发现转移方程变得极其尴尬dp[n-1]不能简单地由dp[n-2]和dp[n-3]推出因为“第0间和第n-1间”之间的依赖关系绕了一圈把线性结构的前缀性给打断了。解环题的通用思路就一句话把环拆成线让已知解法重新生效。因为约束只多了一条“首尾不能同时偷”那么我们可以把所有合法方案划分成两个互不重叠的子集子集一不偷第0间房子。那么第n-1间和第1间之间自然没有环的约束整个问题退化成对nums[1:]从第1间到最后一间做线性打家劫舍。子集二不偷第n-1间房子。那么第0间到第n-2间构成一个线性问题也就是对nums[:n-1]做线性打家劫舍。两个子集加在一起覆盖了所有不违反“首尾不同偷”的方案答案就是这两个子问题结果的较大值。3.2 拆成两个子问题的边界细节这个方法理论上很简单但边界条件藏了一堆暗坑。最典型的情况是数组长度为1时只有一间房子它既是头也是尾没有“相邻”的概念直接返回nums[0]即可。如果你不做特判就去计算max(rob(nums[1:]), rob(nums[:-1]))会发现切片出来全是空数组或单元素结果可能变成0答案直接错误。其次是长度为2的边界但这个问题可以通过rob_range内部的逻辑天然解决不需要额外写。我通常建议把198题的rob逻辑封成一个rob_range函数专门处理一个区间数组这样213题的主逻辑就变得非常清爽from typing import List class Solution: def rob(self, nums: List[int]) - int: if len(nums) 1: return nums[0] return max(self.rob_range(nums[:-1]), self.rob_range(nums[1:])) def rob_range(self, nums: List[int]) - int: prev2, prev1 0, 0 for num in nums: cur max(prev1, prev2 num) prev2, prev1 prev1, cur return prev1注意rob_range里的滚动变量初始化为prev20, prev10这比198题里的初始化方式更通用当数组为空时返回0当数组只有一个元素时第一轮循环cur就是max(0, 0num)num自动得到正确答案。这样213题里所有切片情况都被rob_range优雅地吸收了。再强调一下为什么是取两个子问题的max而不是min因为set一和set二不需要互相排斥某一种最优解可能同时存在于两个子集中比如“首尾都不偷”的方案会同时被两个子集包含但这不影响最终答案——我们需要的是覆盖所有合法方案之后取最大值而不是划分互斥子集。有一点像“容斥”但比容斥简单得多两个子集的并集是全集这就够了。3.3 封装修复后的代码组织技巧很多人刷题的时候忽略了一个代码组织上的细节把“求线性数组最大收益”的逻辑抽成独立函数这个习惯的价值在213题里体现得淋漓尽致。如果直接在213题的rob里复制两份198题的主体代码代码会变得冗长且容易在边界条件上出错。封装成rob_range之后213题的主体只剩两行一个特判一个max调用。这种“先解决子问题再组合子问题”的思维其实就是动态规划之外的另一种核心能力——分治与抽象。面试里如果你能把代码写成这样面试官很容易看出你理解了问题的本质而不只是背会了题解。当然也有另一种实现方式不用切片而是在递归函数里传入left和right两个下标来表示区间。这样可以避免切片带来的额外空间开销。在LeetCode上切片的开销其实可以忽略但如果你在面试中聊到“如何避免切片、用索引传参”会是一个不错的加分小细节。4. 打家劫舍III树形DP与二叉树状态机4.1 从线性推导到树上后序遍历的思路转变打家劫舍IIILeetCode 337是这套题里最有“脱胎换骨”感觉的一道。房子不再排成数组而是构成一棵二叉树父节点和子节点是相邻住户不能同时被偷。也就是说如果你偷了某个节点那么它的左右孩子都不能偷但如果你不偷某个节点它的左右孩子可以各自独立选择偷或不偷。这个变化直接废掉了线性DP里的“下标递推”思想因为树没有“前一个、后一个”的顺序概念只有父子层级。面对树结构我们自然想到用递归去遍历。这里的核心问题是递归函数该返回什么最直接的思路是传一个布尔参数表示“父节点有没有被偷”然后根据这个参数决定当前节点能不能偷。这个方案可行但代码写起来很别扭还需要同时处理左右子树之间不同的约束。更优雅的做法是让递归函数返回两个值一次把“偷当前节点”和“不偷当前节点”两种状态下的最优收益都带回来。这样父节点不需要知道孙子节点内部的复杂决策细节只需要组合两个孩子的返回值即可。在遍历方式上必须选择后序遍历先处理完左子树和右子树再处理根节点。因为根节点的状态取决于孩子节点返回的状态如果先处理根节点手里的数据根本不够用。这种“父节点依赖子节点”的依赖关系在后序遍历中可以天然满足。4.2 返回值用[不偷,偷]二元组的写法详解直接给出可运行的代码from typing import Optional class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def rob(self, root: Optional[TreeNode]) - int: def dfs(node): if not node: return [0, 0] # [不偷当前节点, 偷当前节点] left dfs(node.left) right dfs(node.right) # 当前节点不偷左右孩子各自取最优 not_rob max(left) max(right) # 这里偷懒了其实应该是 max(left[0], left[1]) max(right[0], right[1]) # 当前节点偷左右孩子都只能不偷 rob node.val left[0] right[0] return [not_rob, rob] return max(dfs(root))等一下上面的max(left)写法有个隐藏bugmax([a, b])没问题它确实会取两个元素的最大值但这样写容易让后来的阅读者混淆批阅代码时一眼看不懂意图。更明确的写法是not_rob max(left[0], left[1]) max(right[0], right[1])我把两种写法都摆出来是想提醒你算法题里最怕的就是“乍一看对但逻辑不透明”的写法。虽然max(left)在Python里确实能把二元列表的最大值求出来代码也短但在面试和代码review场景下清晰的意图远比省几个字符重要。这个后序返回值写法的精妙之处在于每个节点只需要关心自己偷与不偷两种结果不需要知道子树内部具体怎么曲折。父节点拿到的两个数字就像交易报价单一样只要把各种组合算一遍取max就行。从根节点开始一路递归到叶子叶子返回[0, 0]到父节点再层层组合回传最后答案就是根节点两个状态里的较大值。时间复杂度是O(n)每个节点恰好访问一次空间复杂度是O(height)即递归栈深度。如果是极端不平衡的链状树递归深度可能达到nPython默认递归深度是1000上下遇到超深数据要注意。这个我在第五部分再细说。4.3 记忆化搜索路线与后序路线的对比树形DP还有另一条常见路线按“爷爷-儿子-孙子”的跨度去建立状态。因为不能偷相邻父子所以某个节点的最优解有两种可能偷这个节点那么收益等于node.val加上所有孙子的最优解不偷这个节点那么收益等于所有儿子的最优解之和。写成状态就是dp[node] max( node.val sum(dp[孙子节点]), sum(dp[儿子节点]) )这个思路直观但实现起来需要访问node.left.left、node.left.right、node.right.left、node.right.right判空判到怀疑人生。而且如果不加记忆化同一个孙子节点会被不同的路径重复计算效率退化严重。为了克服这个问题可以用哈希表缓存每个节点已经计算过的结果这就是“记忆化搜索”。我推荐直接用二元组后序遍历的写法原因有三不需要额外开辟缓存表天然不会重复计算。不需要操作复杂指针去访问孙子节点代码量大幅减少。它把“状态的概念”直接融入返回值读者很容易理解“当前节点偷/不偷”是两种独立状态为后续学习股票买卖等更复杂状态机DP打基础。从设计上看二元组后序遍历更贴近“状态机DP”的思维范式每个节点携带一组状态向量父节点做的事情本质上是在做状态转移。这个模式会在“打家劫舍III→股票问题→树形DP进阶题”这些更难的题目中不断复现。5. 高频错误、面试追问与同类题扩展5.1 刷题现场最容易踩的五个坑把这三道题刷下来我总结了几个最容易犯的错误有些是我自己在本地调试时栽过的有些是帮别人看代码时见过的错误类型错误写法正确做法198题忘记判空数组直接取nums[0]先判断len(nums)0返回0198题单元素边界dp[1]越界单独处理n1返回nums[0]213题n1没特判切片算完得到0直接return nums[0]337题的返回顺序混淆返回[偷,不偷]导致父节点组合出错固定返回[不偷,偷]并加注释说明用贪心思路解法当正解每次选金额最大的房子用DP推导因为贪心无法处理相邻约束的连锁影响最后一条值得多说一句。我见过有人对[2, 3, 2]这个用例用“每间隔一轮取最大”的思路先挑3结果两头不能选收益3而DP的结果是偷首尾两家共4。贪心在当前决策时看不见后续影响而动态规划把“偷不偷”的影响全部编进了状态里这是本质区别。面试里如果被问“这道题为什么不可以用贪心”拿这个反例回答就够了。还有一个337题里容易踩的坑是递归栈深度。LeetCode的测试用例很少会故意卡这个但面试官一旦问起来你可以顺势聊一聊迭代版后序遍历怎么做利用显式栈维护状态先遍历树再在出栈阶段收集每个节点返回的二元组。这是一种用空间换递归深度上限的经典解法算一个加分扩展。5.2 面试官最爱追问的变化与应对打家劫舍系列在面试中的变形非常多这里列几个高频追问你可以当成模拟面试准备“如果房子排成的是一个网格怎么办”这是从一维到二维的扩展对应的是二维动态规划。你需要按行或按列压缩状态核心思想仍然是“每一行的选择影响相邻行”复杂度会升到O(mn)。“如果允许连续偷最多k间怎么改”这时状态需要加一个维度dp[i][j]代表前i间房子、已经偷了j次时的最大收益转移时对“偷当前房间”要判断是否突破连续次数限制。“能不能不用递归写337题”这是考验迭代遍历基本功的好问题。把后序遍历改成显式栈模拟或者用Morris遍历思想做空间优化都是可以聊的方向。“如果图是一棵普通多叉树呢”只要还是树结构二元组后序遍历就能无缝套用。因为约束只发生在父子节点之间孩子数量不影响状态定义。这些追问背后有个共同点它们都在考察你是不是真正掌握了“定义状态、分析转移、确定遍历顺序”这三个动作而不是只会背模板。所以刷这三道题时我强烈建议你每道题都亲手把状态定义和转移方程写在纸上再对着代码验证一遍。这个过程虽然慢但收益远比多刷十道简单题大。5.3 从打家劫舍到股票买卖一类状态机题的规律打家劫舍III里的二元组写法和LeetCode股票买卖系列里的“持有/不持有”状态本质上是一回事。在股票问题中你在第i天要决定买入、卖出、还是持有每笔交易会改变你的状态在打家劫舍里你面对每间房要决定偷还是不偷这个决策也构成状态之间的跳转。把多个状态用转移箭头连起来就形成了所谓的“状态机DP”。总结一个我从打家劫舍系列提炼出来的通用套路把所有可能的“局面”都列出来作为状态比如偷/不偷、持有/空仓、选/不选。写出状态之间的转移关系注意哪些决策会改变状态、哪些决策保持不变。确认初始状态和边界条件也就是dp表的起点。找正确的遍历顺序——数组从前往后树用后序遍历环拆成线。这套方法不仅能应付打家劫舍系列还能一路平推股票买卖、部分打家劫舍IV的变体、以及不少面试中的即兴DP题。做题做到最后你会发现DP题目虽然千变万化但核心骨架始终是稳定的变的只是状态和转移的花样。最后聊一点个人的练习心得我刷这三道题的时候有一个习惯不急着看题解先自己把dp数组的规模、每个下标的意义写在纸上然后从最简单的情况开始推。比如198题我会先手写n1、n2、n3时的结果再上代码。这样做的好处是一旦理解了状态定义代码只是状态定义的翻译而不是死记下来的模板。另外一个很有用的技巧把“打家劫舍I的空间优化版本”当成一个标准工具函数存在脑子里。后面做环形、甚至做二维扩展时这个函数的变体还会反复出现。刷题不是比谁刷得多而是比谁能从一道题中提取出可以复用的思维模型。打家劫舍系列就是那种特别适合做这种提取的题目因为它的模型足够简单又足够有代表性。如果你正准备面试建议把这一系列在LeetCode上的“提交记录”也保留下来偶尔回看自己当时的写法能很明显地看到思考水平的进步。祝刷题顺利面试点满。