看到「198. 打家劫舍」这个标题做过算法题的朋友应该一秒就能对上号——这是动态规划里最经典的入门题之一。题目本身不复杂一条街上若干房屋每间屋放着数额不等的现金但相邻两间屋装了联动报警器同一晚进入相邻两家就会触发警报问一次行动不惊动警报的前提下最多能偷到多少钱。很多新手第一次做这题容易被人设带偏要么想着暴力枚举所有组合要么凭直觉“隔一家偷一家”就算完。实际上真正把它做明白你会掌握动态规划最重要的两件事怎么定义状态怎么推导转移方程。这两个能力放到后面的背包问题、区间DP、树形DP里全都用得着。这篇博文适合刚开始学算法、正在刷动态规划的初学者也适合面试前想快速过一遍经典题的候选人。1. 先看清题目一排房子、一个报警器、一个最大金额1.1 核心需求输入输出与关键约束先把这个题翻译成最朴素的描述。你有一个整数数组numsnums[i]表示第i间房屋里存放的现金数量。你要从这些房屋中选出一个子集子集里不能出现相邻的两间房目标是让选出来的金额之和最大。举个例子nums [2, 7, 9, 3, 1]一种最优选择是偷第 0 间、第 2 间和第 4 间得到2 9 1 12。你看这中间跳过了第 1 间和第 3 间说明选的并不是“每隔一间就偷一间”这种机械规律真正的最优路径需要根据不同金额动态调整。题目只要求输出最大金额不需要你打印偷了哪些房子。这意味着我们只关心“最优值”不关心具体方案所以这类题非常适合动态规划——不用去枚举所有合法子集只维护每一步的最优结果即可。输入数组长度可能为 0也可能只有 1 间房这两种边界情况刷题时很容易被忽略后面我会单独拿出来讲。1.2 为什么说它是动态规划的代表题判断一道题适不适合用动态规划关键是看它有没有两个特征重叠子问题和最优子结构。先说重叠子问题。假设你正站在第i间房门口你面临的选择无非是偷或者不偷。如果偷了下一间能考虑的最早位置是i2如果不偷下一步就走到i1。你会发现不管是从i出发也好从i1出发也好后面要面对的决策结构是完全一样的只是起点不同。这意味着同一个子问题会被反复遇到比如走到第 5 间房的最优解可能既被“从第 3 间不偷然后走到这”用过又被“从第 4 间不偷然后走到这”用过。再说最优子结构。如果我知道“从第i-2间及之前能偷到的最大金额”和“从第i-1间及之前能偷到的最大金额”我就能推导出“到第i间为止的最大金额”。原因是当前决策只和前两个状态挂钩要么沿用上一次的最优结果要么加上当前房的钱并继承上上次的最优结果。局部的“最优”能够一层层组合成全局的“最优”不存在跨多个状态的复杂依赖。这两个特征凑齐问题基本上就从“指数级枚举”变成了“线性递推”。这也是打家劫舍能成为动态规划入门题的原因它没有背包问题里的容量维度也没有区间DP里的括号配对啊、区间合并啊这些花活纯粹的“选或者不选”就是线性DP最本来的样子。2. 核心思路拆解从暴力递归一步步走到动态规划2.1 暴力递归先写最直觉的解法很多人拿到题的第一反应是穷举。把每条街上所有“不相邻”的子集都列出来计算各自的金额总和取最大值。但房子数量一多这个方案立刻失效每个房子都有两种状态偷/不偷还需要额外限制相邻约束枚举量是O(2^n)级别的。如果街上有 30 间房光是组合数就已经超过十亿等它跑完黄花菜都凉了。不过在写动态规划之前我建议你先写一个暴力递归版本因为它能帮你把决策逻辑理清楚。定义一个函数dfs(i)表示“从第i间房开始一直走到街尾能偷到的最大金额”。站在第i间房你只需要比较两种选择偷第i间收益是nums[i] dfs(i2)因为偷了这间下一间只能从i2开始考虑不偷第i间收益是dfs(i1)直接跳过这间。最后取这两者的最大值。这个递归思路和原题逻辑是一一对应的代码写出来也很短def dfs(i): if i len(nums): return 0 return max(dfs(i 1), nums[i] dfs(i 2))这段递归本身没有错错在效率。它把同一个状态反复计算了很多遍。比如dfs(3)既会被dfs(1)通过“偷第 1 间”这条路径调用也会被dfs(2)通过“不偷第 2 间”这条路径调用。随着递归深度增加重复计算量呈指数增长。2.2 状态定义dp[i] 到底存什么递归慢是因为没有把已经算过的结果记下来。那我们把每一步的结果存进数组这就是动态规划的雏形。这里最关键的是怎么定义状态。我见过不少初学者把dp[i]定义为“必须偷第 i 间房时的最大金额”结果发现转移特别别扭因为你还得额外记录第i-1间到底偷没偷。最舒服的定义是dp[i]表示前 i 间房也就是下标0到i-1能偷到的最大金额。注意这个“前 i 间房”的表述。它不是“第 i 间房”而是“把前 i 间房全部考虑一遍之后的最优结果”。这样定义有几个天然的好处dp[0] 0因为前 0 间房没有任何钱可偷dp[1] nums[0]因为只有一间房时最大金额就是这一间的钱最终答案就是dp[n]其中n是数组长度代表全街的最优结果。用“前 i 间房”而不是“偷到第 i 间为止”可以避免纠缠最后一间房到底偷没偷。你只需要知道“前 i 间房的最优值”是多少至于它是靠偷第 i-1 间实现的还是不偷它实现的都没关系。这个思想在动态规划里叫“状态压缩”把不重要的信息丢掉只保留影响后续决策的核心信息。2.3 状态转移方程是怎么推出来的状态定义好了接下来就是整道题的心脏转移方程。考虑计算dp[i]也就是前i间房的最优值。第i-1间房最后一间只有两种处置方式第一种不偷第i-1间。那么前i间房的最优值就等于前i-1间房的最优值即dp[i-1]。第二种偷第i-1间。偷了它第i-2间房是绝对不能碰的否则会触发报警。所以收益由两部分组成前i-2间房的最优值加上第i-1间房里的现金。也就是dp[i-2] nums[i-1]。这两种方案谁大选谁于是得到dp[i] max(dp[i-1], dp[i-2] nums[i-1])这个式子看起来简单很多人会背但未必理解为什么只需要看dp[i-1]和dp[i-2]而不用管更前面的状态。原因在于dp[i-1]本身就是一个“已经把所有可能方案都考虑清楚后的最优结果”它内部可能偷了第i-2间也可能没有但无论哪种情况它都已经保证了“前i-1间房合法且最优”。所以在“不偷第i-1间”这条分支里前人已经帮我们做完了所有决策直接继承即可。这个思路可以类比成一个“账本维护”过程你每天都要记一下到今天为止累计能赚到的钱面对新的一天要么选择“维持昨天的账本”要么选择“前天的账本加上今天的收入”。因为你不能连续两天赚钱所以新账本只依赖昨天和前天的旧账本。2.4 复杂度分析时间已经最优空间还能再省按照上面的转移方程数组长度是n每个dp[i]只需要常数时间计算所以总时间复杂度是O(n)。这个复杂度已经是最优的了因为无论用什么方法每个房子至少要被看一次少于O(n)连数据都读不完。空间方面如果开一个长度为n1的dp数组空间复杂度是O(n)。但注意转移方程里dp[i]只依赖dp[i-1]和dp[i-2]也就是说往前数第 3 个、第 4 个状态根本用不上。既然是这种情况我们完全可以把空间压缩到O(1)只保留两个滚动变量。这也是面试里常见的追问点你能不能写一个空间 O(1) 的版本能写出来说明你是真的理解了转移方程而不是在背模板。下一节我会把两种写法都放出来。3. 代码实操从一维DP到O(1)空间的手写过程3.1 基础版直接用一维数组实现先用最简单的写法方便对照转移方程理解逻辑。def rob(nums): n len(nums) if n 0: return 0 dp [0] * (n 1) dp[0] 0 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[1] nums[0]因为前 1 间房就是第 0 号房只有这一间可以偷金额自然是nums[0]。为什么循环从i 2开始因为i 1已经初始化过了继续从它开始会出现dp[-1]的越界问题。有的同学习惯把dp数组开成和nums一样长用dp[i]表示“偷到第 i 间为止的最大金额”那转移方程就写成dp[i] max(dp[i - 1], (dp[i - 2] if i 2 else 0) nums[i])这样也能得到正确答案但需要额外处理i 0和i 1的边界情况代码稍显啰嗦。我个人更推荐“前 i 间房”的写法因为dp[0] 0这个天然的空集状态让边界处理变得非常干净。3.2 空间优化版只用两个变量滚动从转移方程可以看出未来无论计算多少个dp[i]真正需要的永远只有“上一个值”和“上上一个值”。于是我们可以用prev1表示dp[i-1]用prev2表示dp[i-2]每遍历一个新房子就算出当前值cur然后整体前移一格。def rob(nums): prev2 0 # dp[i-2] prev1 0 # dp[i-1] for num in nums: cur max(prev1, prev2 num) prev2 prev1 prev1 cur return prev1这个版本里prev2初始是0对应dp[0]prev1初始也是0对应“还没遍历任何房子时”的dp[-1]把它当成 0 来用刚好符合空街没有钱的设定。遍历第一个房子时cur max(0, 0 nums[0]) nums[0]和基础版的dp[1] nums[0]完全一致。为什么能这样压缩本质上是因为转移方程的“依赖半径”只有 2。这是一个非常通用的观察只要某个线性DP的状态只依赖紧邻的前 k 个状态就能用 k1 个滚动变量代替整个数组。以后做别的题目时你可以先写数组版本跑通再观察依赖关系最后压缩空间这是一个很稳的流程。3.3 手动走查带着两个例子算一遍代码写出来是一回事能徒手把过程推出来是另一回事。我用两个用例带大家走一遍这样不管以后面试还是自己复习都能快速验证代码是否正确。第一个例子用原题常见的nums [2, 7, 9, 3, 1]。i当前房子金额dp[i-1]dp[i-2] 当前金额dp[i]0---01200 2 222720 7 773972 9 111143117 3 1011511111 1 1212最终答案是 12。注意看第 4 步dp[4]算出来还是 11因为偷第 3 间30 号这里用下标说明当前房子的下标是 3 的话的收益不如沿用之前的 11 大。这说明转移方程里的max操作天然帮我们做了“要不要换一种决策”的判断。第二个例子我强烈建议新手亲自走一遍nums [10, 1, 1, 10]。直觉上很多人会想“隔一家偷一家”那就偷第 0 间和第 2 间得到 11。但实际上最优解是偷第 0 间和第 3 间得到 20。我们用滚动变量的逻辑推一遍初始化prev2 0, prev1 0遇到 10cur max(0, 010) 10两个变量变成prev20, prev110遇到 1cur max(10, 01) 10两个变量变成prev210, prev110遇到 1cur max(10, 101) 11两个变量变成prev210, prev111遇到 10cur max(11, 1010) 20两个变量变成prev211, prev120最终答案是 20。这个例子揭示了一个重要事实最优路径不一定是“隔一个偷一个”它可能会连续跳过两个甚至更多房子。因为第 1 间和第 2 间的价值太低为了能偷到最后的 10我们宁可放弃它们。这也顺便解释了为什么贪心算法在这里不成立——每一步做局部最优选择无法预见到后面更高价值的房子。4. 我踩过的坑边界、滚动变量与贪心误区4.1 空数组和单元素看似简单却容易翻车空数组这种边界没有经验的人很容易忽略。如果nums []整条街没有任何房子能偷到的最大金额显然是0。但如果在基础版代码里直接访问nums[0]或者初始化dp[1] nums[0]程序就会崩溃。单元素数组也有隐藏问题比如nums [5]。最优解当然就是 5但如果你的循环从i 2开始并且没有对n 1做处理那么dp数组长度为 2dp[1] nums[0]之后循环不执行返回dp[n] dp[1] 5这个反而没问题。真正容易翻车的是空间优化版里for num in nums的写法如果数组为空循环体不执行prev1保持 0返回 0反正是正确的。所以我更推荐滚动变量版它在边界上天然安全。不过要提醒一句如果面试官要求你写“能处理所有边界”的版本你最好在代码开头显式判断n 0和n 1不要依赖某个写法的巧合。因为代码的可读性和明确性比耍小聪明更重要。4.2 滚动变量更新顺序一个隐蔽的经典错误空间优化版最阴险的坑就是更新顺序。假设你写了下面这段代码cur max(prev1, prev2 num) prev1 cur prev2 prev1乍一看好像没问题先算cur再更新prev1然后更新prev2。可你仔细想想第二行执行完之后prev1已经变成了cur第三行再执行prev2 prev1那prev2也变成了cur。下一轮循环里prev2不再代表“上上轮”的值了而是和prev1一样都是本轮的值整个递推关系就崩了。正确写法应该是先把prev1的旧值保存下来再更新两个变量cur max(prev1, prev2 num) prev2, prev1 prev1, curPython 的多重赋值会先取右侧的旧值再依次赋值所以能安全完成交换。在其他语言里你可能需要一个临时变量int temp prev2; prev2 prev1; prev1 cur;这个错误之所以隐蔽是因为部分用例恰好能跑出正确结果。比如在一个严格递增的数组上prev2 num一直更大prev1 cur和prev2 prev1交错之后结果可能看起来依然是对的。但换个用例就原形毕露。我建议每次写滚动变量时多检查两个变量的更新顺序或者干脆先用数组版本验证再改成滚动版本。4.3 递归方案为什么不适合实战但适合讲思路有些初学者会执着于用递归加记忆化。实现大概是def rob(nums): memo [-1] * len(nums) def dfs(i): if i len(nums): return 0 if memo[i] ! -1: return memo[i] memo[i] max(dfs(i 1), nums[i] dfs(i 2)) return memo[i] return dfs(0)这个写法的时间复杂度也是O(n)空间复杂度是O(n)并没有错。但实际面试和刷题时我一般不推荐用它作为最终提交版本原因有两个一是递归会占用系统调用栈数组特别长时存在栈溢出的风险二是记忆化数组加递归跳转代码比滚动变量的版本长解释起来也更绕。不过如果你在面试时被问到“能不能讲一下思路”从递归开始讲其实是个很好的策略。先写暴力递归点出重复计算的问题再说可以用记忆化解决最后说“其实我们只需要保留前两个状态可以优化到 O(1) 空间”整个思考链条非常完整。这是面试官最喜欢看到的解题过程。4.4 排序和贪心这些错误直觉趁早放弃我在讨论区见过不止一个人尝试“先把金额排序然后隔一个取一个”理由是“反正不能拿相邻的那我把金额大的都挑出来”。可问题是一旦排序你就失去了房子在街道上的相邻关系。比如nums [2, 1, 1, 2]正确答案是偷第 0 间和第 3 间得到 4。如果先排序变成[1, 1, 2, 2]按“隔一个取一个”选下标 0 和 2得到 3如果手动挑两个最大的 2它们在排序后是新下标 2 和 3相邻了又不合法。所以排序这条路根本走不通。还有一个常见直觉是“分别计算偶数下标之和与奇数下标之和取较大者”。这个想法在少数用例上碰巧正确比如[2, 7, 9, 3, 1]的奇数位和是 10偶数位和是 11但正确答案是 12因为最优路径其实是从偶数位、奇数位、偶数位交叉着选的。动态规划的本质就是允许这种看似杂乱无章的选法只要它满足不相邻约束并且总和最大。4.5 其他语言的数值溢出问题如果用 C 或 Java 写这道题需要注意数组元素相加后的数值范围。正常情况下题目会限定nums[i]在int范围内但如果数组很长、金额又大dp[i-2] nums[i-1]有可能超过int。一旦溢出变成负数max的比较就完全失去意义。稳妥的做法是使用long类型来存储dp值最后再转成int返回或者干脆全程用long。Python 不存在这个问题因为它的整数是任意精度的。如果你在刷力扣风格的题目不用太担心这个但如果是在给生产项目做数值计算类型范围一定要提前考虑清楚。4.6 扩展思路环形与树形版本怎么继续打打家劫舍是个系列题吃透 198 之后后面两道也顺手很多。第一道是房屋围成一圈的环形版本编号一般是 213。首尾的房子也是相邻的所以第一间和最后一间不能同时偷。解法很巧妙既然问题是首尾冲突那就拆成两种情况分别求最大金额——一种是不偷第一间另一种是不偷最后一间。两个结果取较大值就行。本质上还是 198 的线性 DP只是多添了一次调用。第二道是树形结构房子分布在一棵二叉树上直接相连的两个节点不能同时偷。这个就需要用“树形DP”递归遍历每个节点对每个节点维护两个状态偷它时的总金额不偷它时的总金额。父节点可以根据左右子节点返回的四个状态推导出自己的两个状态。这个题相比 198 要复杂不少但核心思想仍然是“选或不选”的决策只是从数组变成了树的形态。4.7 最后一点经验怎么把这题变成自己的如果让我给一个刷题建议我会说不要直接背转移方程先拿几个数组在纸上推一遍。你自己手算[10, 1, 1, 10]的过程比盯着代码看十遍都有用。因为只有亲手算一遍你才会发现“最优方案居然跳过了两个房子”这种领悟是背题背不出来的。面试的时候不管对面怎么追问答题顺序都可以固定下来先讲暴力递归说明有哪些重复计算再讲记忆化把复杂度降到O(n)最后讲滚动变量秀出O(1)空间。这个过程既展示了你的思路演进又体现了对空间优化的敏感度。我个人有个习惯每次写完这类线性 DP会顺手问自己一句“如果状态依赖从前两个变成从前三个代码应该怎么改”。想清楚这个问题你对滚动变量的理解就不只是背代码而是真正掌握了一套处理此类问题的通用技能。这题的代码量很小但它承载的思考方法足够你在后面很多题目里反复受益。
复杂度详解)
