打家劫舍这道题可以说是动态规划入门路上绕不开的一站。力扣198题也是LeetCode热题100里的常客很多人第一次系统学DP就是靠这道题把状态转移方程这个概念真正吃透的。题目本身读起来像个小故事一条街上的房屋排成一列每间房里有不同金额的现金你不能连续闯两间相邻的房屋否则会触发警报问一晚上最多能带走多少。初看会觉得很简单无非是隔一家偷一家但真正动手写代码的时候才发现事情没这么简单。这个问题的本质是从一个数组中选出一组“互不相邻”的下标让对应元素的和最大属于典型的最优化问题。暴力枚举所有组合是指数级的而动态规划恰好能把整个过程压缩成一次线性扫描。这篇文章我会从题目拆解、状态定义、代码实现、常见坑点、变种扩展五个部分把我在刷这道题时的思考过程完整写出来。不管你是刚接触DP的初学者还是想在面试前快速过一遍经典题这篇都应该能帮你少走一点弯路。1. 题目到底在问什么把场景翻译成数学模型1.1 题目描述与输入输出示例先看原题描述你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下一夜之内能够偷窃到的最高金额。举个例子输入nums [1,2,3,1]输出应该是4。为什么是4对应偷法有很多比如偷第0间和第2间金额134或者偷第1间和第3间金额213。明显4更大。再看nums [2,7,9,3,1]输出12对应偷第0、2、4间29112。这两个示例其实已经把关键信息暴露了不能简单地从左到右每隔一个取一个。第二个示例如果傻乎乎从0号开始隔一个取得到2911漏掉了最后的1如果从1号开始隔一个取得到7310也不是最优。最优方案需要全局权衡而不是固定步长可以解决的。1.2 为什么贪心在这里靠不住我第一次做这道题时最大的误区就是想用贪心每次对比相邻两间房谁钱多先抢钱多的那间。这种思路看起来很自然钱多的房子贡献大嘛。但贪心只看眼前局部最优很容易丢掉全局最优。举个反例nums [2,3,2]。中间的房子钱最多有3块。如果贪心先选中间的那么因为相邻约束两边都不能选最终收益只有3。但你完全可以选两边的2和2加起来是4比单独偷3更多。这个例子非常经典它说明了一个重要现象有时候局部看起来“亏了”的选择组合起来反而是最优。这正是动态规划登场的原因。DP不急着做“当下决策”而是把每一步的“最优结果”都算出来存好等后面需要时直接取用。它解决的是一类有约束、有取舍、需要全局最优的问题打家劫舍就是最典型的代表。2. 状态定义与转移方程DP的核心步骤2.1 定义dp[i]之前先想清楚要记录什么动态规划第一步永远都是定义状态。很多初学者会写“dp[i]代表前i间房能偷的最大金额”这个定义本身没问题但有个细节容易模糊计算dp[i]时需不需要知道第i间房到底偷没偷答案是不需要。力扣标准解法里dp[i]表示“从第0间到第i间即前i1间房能偷到的最大金额”它只记录截止到这一间时的最优结果并不过问最后一间的具体动作。比如nums[2,3,2]dp[0]2只有一间偷了它dp[1]max(2,3)3前两间取钱多的dp[2]max(dp[1], dp[0]2)max(3,4)4。这里的4对应“偷第0间和第2间”而计算过程中完全不关心dp[1]到底是怎么得到3的。这种状态设计的高明之处在于它把每间房偷或不偷的细节都揉碎打包成一个“前缀最优值”。转移时只需要看前两个状态不需要记住具体选了哪些下标大大简化了问题。2.2 转移方程是怎么一步步推出来的对于第i间房只有两种选择偷或者不偷。如果偷第i间那么第i-1间一定不能碰收益就是dp[i-2] nums[i]。如果不偷第i间那么第i-1间随便怎么处理收益就是dp[i-1]。两个选择取较大值转移方程就出来了dp[i] max(dp[i-1], dp[i-2] nums[i])这里我想特别解释一个容易困惑的点为什么偷第i间时用dp[i-2]就一定安全因为dp[i-2]表示截至第i-2间的最优值它内部可能偷了第i-2间也可能没偷。偷了的话第i-2间和第i间中间隔着第i-1间不相邻没偷的话就更没冲突了。所以无论dp[i-2]内部怎么选都不会和第i间打架。同理不偷第i间时用dp[i-1]因为第i间根本不参与第i-1间无论怎么选都不会影响后面的结果。这就是动态规划里的“无后效性”当前决策只影响未来一步已经算好的状态值不需要回头修改。2.3 初始化和遍历顺序怎么定有了方程还要处理边界。一个比较清爽的约定是让dp[i]表示前i间房的最优值注意这里i从0到n数组长度开 n1。dp[0] 0前0间房自然偷不到任何钱。dp[1] nums[0]只有一间房时只能偷它。从 i2 开始转移dp[i] max(dp[i-1], dp[i-2] nums[i-1])注意这里用nums[i-1]是因为下标偏移了一位。遍历顺序是从左到右递增i。因为dp[i]只依赖dp[i-1]和dp[i-2]天然满足无后效性只需要一趟循环就能把所有状态算完。这种约定比处理 n1、n2 的if分支要干净得多也更容易扩展到变种题。3. 代码实现从朴素数组到滚动变量3.1 最容易理解的数组版本先给一个最直白的Python写法逐个状态存进数组from typing import List def rob(nums: List[int]) - int: n len(nums) if n 0: return 0 if n 1: return nums[0] 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]) return dp[-1]这个写法逻辑最直观适合用来对照状态转移方程理解。Java版也差不多class Solution { public int rob(int[] nums) { int n nums.length; if (n 0) return 0; if (n 1) return nums[0]; int[] dp new int[n]; dp[0] nums[0]; dp[1] Math.max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] Math.max(dp[i-1], dp[i-2] nums[i]); } return dp[n-1]; } }但我个人更喜欢用“偏移一位”的写法因为边界判断更少代码更整齐def rob(nums: List[int]) - int: if not nums: return 0 n len(nums) 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[i]表示前i间房的最优值。空数组直接返回0n1时循环不执行返回dp[1] nums[0]n2时循环执行一次dp[2] max(dp[1], dp[0] nums[1])也就是max(nums[0], nums[1])完全正确。三个边界在一条逻辑里全部覆盖了这就是偏移位定义的好处。3.2 空间优化滚动变量到底在滚什么观察转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你会发现每个新状态只依赖前两个状态。再往前的数据一辈子都用不到了开一整个数组就是浪费。优化方案是用两个变量滚动def rob(nums: List[int]) - int: prev2 0 # 相当于 dp[i-2] prev1 0 # 相当于 dp[i-1] for x in nums: cur max(prev1, prev2 x) prev2 prev1 prev1 cur return prev1这里prev2和prev1是两个“滑动窗口”每处理一间房就整体往前滚一格。第一次遍历时prev20表示前0间房收益0prev10表示“前-1间房”也当0处理这样第一个元素进来时cur max(0, 0 nums[0]) nums[0]正好对应dp[1]。滚动变量版本有个很容易踩的坑变量更新顺序。很多人写成prev1 cur prev2 prev1 # 错prev2被覆盖成cur了这样下一轮计算时prev2已经不是原来的dp[i-2]了结果必然出错。正确的顺序一定是先更新prev2再更新prev1。这个顺序问题我刷题时翻过车写出来提醒一下。学会了滚动写法空间复杂度从O(n)降到O(1)面试官追问优化时就能从容应对。3.3 复杂度分析时间和空间各是多少无论用数组还是滚动变量每个房间都只处理一次所以时间复杂度都是 O(n)其中n是房屋数量。空间上数组版是 O(n)滚动变量版是 O(1)。力扣这题数组长度最大也就100数组版完全够用但滚动版本能帮你理解状态压缩的思路对后面做更多DP题很有帮助。另外要注意nums的长度可能为0这在调用nums[0]前必须判断。还有题目给的是非负整数数组金额本身不会拖后腿但如果变种题里出现负数就要重新考虑状态定义这个我在下一节细讲。4. 常见坑点与调试经验五个我踩过的坑4.1 空数组和长度1的边界处理这题最容易翻车的点就是边界。很多人的第一版代码长这样dp[0] nums[0]如果nums是空数组这行直接IndexError。所以我在文章里推荐偏移一位的写法if not nums: return 0从一开始就拦掉了空数组。n1时dp[1] nums[0]也成立循环不执行直接返回nums[0]就完事了。用数组版的读者记得把两个if分支写在最前面顺序不能反先判空再判长度1否则空数组会先挂在nums[0]上。4.2 负数出现时状态定义就失效了198题明确说了数组是非负整数但面试官偶尔会加一句“如果把金额改成可正可负呢”这时候原来的状态定义会出问题。比如nums [-1, -2]按我们的方程走dp[1] -1dp[2] max(-1, 0-2) -1返回-1。但实际上一间都不偷收益是0正确答案应该是0才对。问题出在哪我们的dp[i]默认了“必须在前i间里至少偷一间”没有把“一间都不偷”这个选项编码进去。遇到带负数的变种要么把所有金额跟0取个max要么重新设计状态dp[i]表示前i间房的“最大净收益”可以允许为0。这算是一个很好的面试讨论点能主动提出来会加分。4.3 滚动变量更新顺序写反前面提到过滚动变量版本里prev2和prev1的更新顺序极其关键。我再给一个具体的错误示例for x in nums: cur max(prev1, prev2 x) # 错误顺序先更新prev1 prev1 cur prev2 prev1 # prev2 变成 cur 了这样第二轮循环时prev2被“污染”成了上一轮的cur而不是上一轮的prev1状态就错乱了。调试这种问题最好的办法是在循环里打印每一轮的prev2, prev1, cur肉眼一看就明白谁先谁后。4.4 测试用例怎么设计才靠谱刷题时我总是习惯至少跑这几个用例覆盖所有边界测试输入预期输出说明[]0空数组[5]5只有一间房[2,1,1,2]4选首尾两端[2,3,2]4中间钱多但两边之和更大[1,2,3,1]4标准示例[2,7,9,3,1]12标准示例特别是[2,1,1,2]它很好地验证了“不相邻”约束的实际含义最优解是2 2 4而不是简单地隔一个取。如果你代码能顺利通过这些用例基本就不会栽在边界上了。4.5 数值溢出和数据类型原题约束金额0 nums[i] 400数组长度最多100总和最多40000int完全不会溢出。但做变种题时如果金额放大、长度拉长就要考虑用long甚至高精度类型。面试时主动说一句“198题的数据范围用int安全但扩展场景我会选用更大的类型以规避溢出”这种对数据边界的敏感度是让人眼前一亮的小细节。5. 从一道题到一类题打家劫舍的变种扩展5.1 213题环形房屋怎么破环形打家劫舍几乎是把198改了个约束第一间房和最后一间房现在变成了邻居不能同时偷。乍一看复杂度上去了但其实解法思路很清晰既然首尾冲突那就分两种情况讨论。情况一偷第0间那最后一间绝对不能偷问题变成在nums[0:n-1]上做线性打家劫舍。情况二不偷第0间那最后一间可以偷问题变成在nums[1:n]上做线性打家劫舍。两个结果取最大即可。代码可以直接复用198的线性解法def rob_linear(nums): prev2, prev1 0, 0 for x in nums: cur max(prev1, prev2 x) prev2, prev1 prev1, cur return prev1 def rob(nums): if len(nums) 1: return nums[0] return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))注意当数组长度只有1时nums[:-1]和nums[1:]都会变成空数组这时候两个分支都返回0单独靠max会出错所以长度1的case必须提前处理。这个变种题在LeetCode热门100题里也经常被拿出来串联考察建议刷完198立刻上手。5.2 337题二叉树上的打家劫舍再进阶一步房屋排布从一条直线变成了二叉树每个节点是一间房直接相连的父子节点不能同时偷。这种题叫树形DP乍一看陌生但其实思路和线性版一脉相承。对每个节点我们只需要两个值rob_this偷这个节点时整棵子树能获得的最大收益等于node.val 左子树不偷的最优值 右子树不偷的最优值。skip_this不偷这个节点时那左右子树各取它们的最大收益即可。后序遍历自底向上返回这两个值最后根节点两种情况取最大def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) rob_this node.val left[1] right[1] skip_this max(left) max(right) return (rob_this, skip_this) return max(dfs(root))这里的(rob_this, skip_this)就是每个子树的两个状态转移逻辑和max(dp[i-1], dp[i-2] nums[i])如出一辙。看懂198再做337你会觉得动态规划真的是一通百通。5.3 这类DP题的通用套路刷完198、213、337你会发现它们都长着同一副骨架明确决策是什么偷或不偷。找到约束条件相邻互斥、父子互斥。定义状态从起点到当前位置的最优结果必要时用多个值表达多种情况。写转移方程当前选择加上跳过冲突后的最优值与不做选择取max。处理边界空数组、长度1、首尾冲突、空节点。类似的题目还有最大子数组和53题、按摩师LintCode经典DP等。这类“带约束的最优选择问题”只要状态定义清晰剩下就是体力活。最后分享一个我个人的刷题习惯。每次做DP题我都会先在草稿纸上把dp[i]的含义用一句话写出来确认它到底记录什么、不记录什么然后才写方程。198题看起来简单但状态定义想清楚和想不清楚写代码的时间可能差出半小时。多在这上面下功夫后面遇到再复杂的动态规划你也会觉得没那么吓人。