在力扣LeetCode的动态规划入门题单里198. 打家劫舍几乎是每个人绕不开的第一道经典题。题目给了一排房屋每间房里有不同数额的现金但相邻的两间房连接着警报系统只要同一晚闯入两间相邻房屋就会触发报警要求算出在不惊动警察的前提下能偷到的最大金额。名字听起来有点戏剧化内核却非常干净从一个数组里选出一组不相邻的元素让它们的和最大。这道题在LeetCode热门100题里常驻也是面试里最高频的DP入门模型之一。刷透它你不只是会背一个转移方程而是真正理解“状态怎么定义、决策怎么转移、空间怎么压”这一整条DP解题链路。1. 题目拆解房子、警报与“相邻冲突”1.1 题目到底在说什么先看一个标准的测试用例nums [1, 2, 3, 1]输出是 4。为什么是 4因为你可以偷第 1 间1和第 3 间3结果 1 3 4。不能偷第 2 间2和第 3 间3因为它们是相邻的会触发警报。另一个示例[2, 7, 9, 3, 1]输出 12最优方案是偷 2、9、1加起来 12。这里要强调一个容易忽略的点题目说的是“不能偷相邻的两家”而不是“必须隔一家偷一家”。很多人一开始会误解成“要么偷奇数位要么偷偶数位”于是直接比较下标奇偶的和这肯定是错的。比如[3, 1, 1, 3]奇数位和是 3 1 4偶数位是 1 3 4但正确答案是偷第 1 间和第 4 间即 3 3 6。这说明最优选择在“隔不隔”这件事上很自由你必须让算法自己决策不能靠人工预设模式。所以题目的本质是给定一个非负整数数组从中选取一个子序列要求任意两个被选中的元素在原数组中不相邻使得选中元素的和最大。1.2 第一直觉为什么全都走不通拿到这种题正常人的第一个想法是枚举所有可能的偷法也就是每个房间都面临两个选择——偷或不偷于是总方案数是 2^n。当 n 100 时这个数字大得离谱暴力枚举在竞赛环境里直接超时。这就是为什么题目要求我们用更聪明的办法而不是硬算。那贪心行不行每次都选当前能选的最大金额举个反例[2, 1, 1, 2]。最大金额是 2如果先偷第 1 间2那第 2 间不能偷接下来能偷的是第 3 间或第 4 间偷第 4 间2总收益 4。可如果你一开始忍住不偷第 1 间直接偷第 2 间1和第 4 间2收益只有 3或者偷第 1 间2和第 4 间2收益 4。看起来贪心好像对了但换个例子[2, 1, 1, 3]贪心先偷 2剩下能偷的只有最后的 3总收益 5可实际上偷 1 3 4或者 2 3 5等等2 和 3 之间隔着 1 和 1不相邻所以 2 3 5 就是最优。还得继续找贪心失效的例子[3, 2, 2, 3]贪心先偷第 1 间 3剩下能偷第 3 间或第 4 间3 和第 4 间不相邻第 1 和第 4 不相邻所以偷 3 3 6。但最优其实是第 2 间 2 第 4 间 3 5不对第 1 间 3 第 4 间 3 6 更好。再找一个真正失效的[2, 3, 2, 3]贪心先偷第 2 间 3剩下只能偷第 4 间 3总共 6但偷第 1 间 2 第 3 间 2 4也不行。难点在于贪心没有全局视野它不知道当前这一个选择会对后面造成什么样的连锁反应。这就是动态规划登场的原因——把决策的过程记录下来让每个位置的最优决策都基于之前所有位置的最优结果。2. DP推演状态定义和转移方程是怎么来的2.1 核心认知dp[i] 表示“前 i 间房”能拿到的最大收益动态规划最重要的第一步不是写代码而是想清楚状态数组代表什么。对于打家劫舍最常见的定义是dp[i]表示从下标 0 到下标 i 的这 i1 间房里能偷到的最大金额。注意这个定义里包含一个非常关键的语义dp[i]并不要求第 i 间房一定要被偷。它只是说“如果我只能考虑前 i1 间房最好的结果是多少”。换句话说dp[i]已经替你做好了“偷第 i 间还是不偷”的取舍它存的是两者的最大值。为什么这个定义好用因为你写状态转移时不用再维护额外的标记不需要记住“上一次偷的是哪一间”。所有关于之前决策的信息都被压缩进了一个数字——前 i-1 间的最优值。这就是DP能取代暴力枚举的根本原因它把整个历史抽象成一个状态。2.2 转移方程推导偷还是不偷这是个问题假设现在轮到第 i 间房你要决定偷不偷它这件事只和两件事有关前 i-1 间房的最优结果以及前 i-2 间房的最优结果。如果你决定偷第 i 间房那么第 i-1 间房就绝对不能偷否则报警。所以在这种情况下你的收益是前 i-2 间房的最优收益加上nums[i]即dp[i-2] nums[i]。如果你决定不偷第 i 间房那么第 i-1 间房偷不偷都无所谓你直接继承前 i-1 间房的最优收益即dp[i-1]。最后取这两种决策里更大的那个得到状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])这里有一个初学者会很困惑的地方为什么不考虑“第 i-1 间没偷”的情况下偷第 i 间呢其实这个情况已经被上面的式子覆盖了。当dp[i-1]不偷第 i-1 间时它的值本身就可能来自于dp[i-2]或者更早的状态。而你偷第 i 间的收益是dp[i-2] nums[i]这个式子里已经包含了“前面怎么偷都行只要不碰第 i-1 间”的自由度。所以两种决策合并之后只剩下两个候选值不需要再细分。再往深一层想为什么dp[i]不需要依赖dp[i-3]、dp[i-4]因为约束只有一个“不能相邻”这是局部约束。dp[i-2]已经代表了下标 0 到 i-2 范围内的全局最优它内部必然已经妥善处理了所有相隔规则。因此当前决策只需要看最近的两个状态这也是后面能做空间压缩的根本依据。2.3 边界条件与初始化一件都不能漏有了转移方程还需要初始化。按数组下标来当数组为空返回 0。当只有一间房dp[0] nums[0]直接返回。当有两间房dp[1]应该等于max(nums[0], nums[1])因为两间相邻不能都偷所以只能选金额更大的那一间。有的同学会写dp[1] nums[1]这在数组两元素时其实也能过但如果nums[0] nums[1]比如[5, 1]你至少应该偷 5 而不是 1所以必须是max(nums[0], nums[1])这个初始化的本质是“前两间房的最优解”而不是“第二间房的值”。从i 2开始循环逐个计算dp[i]最后返回dp[n-1]。这就是最朴素的 O(n) 时间、O(n) 空间的版本。2.4 手动推演一遍看懂 dp 表的生长过程光看方程有点抽象拿官方示例[2, 7, 9, 3, 1]手动从头推一遍你就能直观感受到 dp 表是怎么“长”出来的inums[i]dp[i-2] nums[i]dp[i-1]dp[i]当前最优策略02--2偷第 0 间17--7偷第 1 间放弃第 0 间292 9 11711偷第 0 间和第 2 间337 3 101111维持之前的最优不偷第 3 间4111 1 121112偷第 2 间和第 4 间注意看 i3 这一行dp[3]比dp[2]没有增加因为偷第 3 间的话最多只能得到dp[1] nums[3] 7 3 10还不如不偷维持 11。这个例子完美展示了 dp 表“宁可不动也不乱动”的决策过程。最终dp[4] 12正好是题目的输出。整个过程你不需要回溯具体偷了哪些房间因为 dp 数组一路把最优值传递了下来。3. 空间优化从 O(n) 数组到两个滚动变量3.1 为什么 dp 数组有大量“废数据”看一遍转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你会发现计算dp[i]时只需要dp[i-1]和dp[i-2]至于dp[0]到dp[i-3]它们在后续计算中再也不会被用到。这就像你爬山的时候只需要知道当前位置和上一个台阶不需要记住十年前踩过的所有石头。所以开一个长度为 n 的数组完全是一种浪费。当 n 达到 10 的 5 次方甚至 10 的 6 次方时O(n) 的空间虽然也能过但在面试中面试官非常喜欢追问一句“能不能把空间复杂度降到 O(1)”。3.2 滚动数组写法的完整流程滚动数组的思路就是只保留最近两个状态用两个变量prev2和prev1分别充当dp[i-2]和dp[i-1]。初始化时prev2相当于dp[0]赋值为nums[0]。prev1相当于dp[1]赋值为max(nums[0], nums[1])。然后从i 2开始循环。每一轮cur max(prev1, prev2 nums[i]) prev2 prev1 prev1 cur循环结束后prev1就是整个数组的最优解。这个写法在力扣上性能表现非常好时间 O(n)空间 O(1)。这里要特别说明变量更新的顺序必须先取old prev1覆盖到prev2再把cur赋给prev1。如果你写反成prev1 cur prev2 prev1 # 此时 prev1 已经是 curprev2 拿到的是 cur不是真正的 dp[i-1]那下一轮计算时prev2 nums[i1]里用的就不是dp[i-1]而是dp[i]整个方程就错了。这个坑非常隐蔽跑小数组可能看不出来但一旦数据到位结果就会莫名其妙地偏大或偏小。3.3 滚动更新为什么安全一步步模拟给你看还是用[2, 7, 9, 3, 1]走一遍滚动数组初始prev2 2prev1 max(2, 7) 7i2cur max(7, 2 9) 11更新后prev2 7prev1 11i3cur max(11, 7 3) 11更新后prev2 11prev1 11i4cur max(11, 11 1) 12更新后prev2 11prev1 12返回prev1 12。可以看到滚动数组每一步算出的值和之前用完整 dp 数组推演的结果完全一致。因为它本质上只是把“数组”这个外衣脱掉了保留的仍然是同样的计算逻辑。这也是我推荐初学者先在纸上写 dp 数组版本、再改成滚动变量的原因——先把逻辑搞通优化只是形式上的改造。4. 三种语言的完整实现与刷题细节4.1 Python 实现最贴近思路的写法先给一个最容易理解的版本用 dp 数组def rob(nums): 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]这个版本思路直白适合写在注释里解释你的想法。如果你追求执行效率和极致空间直接上滚动数组版本def rob(nums): 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 prev1Python 的写法有一个天然优势列表索引不会越界因为if n 0和if n 1已经拦住所有异常情况。只要边界条件处理好这段代码在力扣上可以直接通过。4.2 Java / C 实现对比Java 和 C 在逻辑上与 Python 完全一致只有语法差异。Java 版本要注意判空否则输入为 null 时直接 NPEclass Solution { public int rob(int[] nums) { if (nums null || nums.length 0) return 0; int n nums.length; if (n 1) return nums[0]; int prev2 nums[0]; int prev1 Math.max(nums[0], nums[1]); for (int i 2; i n; i) { int cur Math.max(prev1, prev2 nums[i]); prev2 prev1; prev1 cur; } return prev1; } }C 版本用 vector本质上和 Java 是同一个思路class Solution { public: int rob(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint dp(n, 0); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] max(dp[i-1], dp[i-2] nums[i]); } return dp[n-1]; } };三种语言在力扣上跑同一个用例结果一致。我的建议是初学者先用 Python 把思路跑通再用 Java 或 C 写一遍因为这两种语言更接近面试手写代码的场景而且能逼你注意判空和越界等细节。4.3 提交时最容易踩的四个坑这道题通过率不低但我在力扣评论区见过很多失败的提交总结下来主要就这四个坑坑典型场景解决方案空数组没处理nums []开头加if n 0: return 0只有一个元素时访问 dp[1]nums [5]先判断if n 1: return nums[0]dp[1] 初始化为 nums[1] 而非 maxnums [5, 1]写成max(nums[0], nums[1])滚动变量更新顺序写反结果忽大忽小先算cur再prev2 prev1最后prev1 cur前两个坑本质是边界条件后两个坑本质是对 DP 语义的误解。我的习惯是写完代码先自己测三个用例空数组、一个元素、两个元素再测长数组。这种测试习惯能帮你省下很多无谓的提交失败。5. 一道题带出一串题变体与DP学习路线5.1 打家劫舍 II环形怎么拆这一题刷完之后下一步一定会遇到 213. 打家劫舍 II。它的变化是把房子排成一个环第一间和最后一间相邻所以你不能同时偷第一间和最后一间。破解的方法是把它拆成两个不环形的问题一个是“不偷第一间”即考虑nums[1:]另一个是“不偷最后一间”即考虑nums[:-1]。分别对这两个数组跑 198 的解法最后取最大值。为什么能这么拆因为环形带来的额外约束只有一个首尾不能同时被偷。那我们就分情况讨论——要么不偷首要么不偷尾这两种情况覆盖了所有合法方案而且每种情况下剩下的房子又变回了线性排列。这就是 DP 中的一个重要技巧把新约束拆成互斥情况逐一击破。5.2 打家劫舍 III二叉树和树形DP再升级一档是 337. 打家劫舍 III房子变成了一棵二叉树父子节点不能同时被偷。这时线性 DP 的数组结构改成树形 DP但决策模型完全一样。每个节点返回两个值偷当前节点的最大收益和不偷当前节点的最大收益然后自底向上合并。def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) # 偷当前节点左右孩子都不能偷 rob_cur node.val left[1] right[1] # 不偷当前节点左右孩子各自取最优 not_rob_cur max(left) max(right) return (rob_cur, not_rob_cur) return max(dfs(root))这个版本的代码很短但背后是标准的树形 DP 思维。当你把 198、213、337 三题连在一起刷完之后会发现它们共享同一个决策模型“当前节点选或不选子问题的最优解怎么组合”。这也是力扣热门 100 题里 DP 板块最喜欢考的类型之一。5.3 DP刷题的建议路线与判断技巧如果你刚开始刷动态规划不要把 198 当成一道题把它当成一个模板。我建议的刷题路线是先刷 198 打家劫舍理解“选/不选”的决策模型能独立推导出转移方程。再刷 70 爬楼梯和 121 买卖股票的最佳时机这俩同样是一维 DP状态定义和转移相对简单可以巩固基本功。之后刷 322 零钱兑换和 300 最长递增子序列这俩开始涉及“对每个状态遍历所有决策”是从一维 DP 向多维 DP 过渡的桥梁。回头再看 213 和 337体会同一个模型在不同数据结构上的变形。判断一道题该不该用 DP就看两个特征一是存在重叠子问题也就是递归解决时同一个状态被反复计算二是具有最优子结构即全局最优总能由子问题的最优组合而成。打家劫舍正好两者都满足所以它才能成为经典中的经典。学到这里你已经掌握了打家劫舍这道题从暴力到 DP 再到空间优化的完整进化路径。我个人在实际刷题中的体会是这题真正的分水岭不在转移方程而在你能不能想清楚“dp[i] 代表前 i 间房的最优值而不是第 i 间房必须偷的值”。想明白这一点后面 213、337 甚至更多变体都会顺畅很多。最后分享一个我自己的小习惯做任何 DP 题先写一行注释把状态定义写清楚再动键盘。状态定义写不出来的题代码写得再漂亮也容易在边界上翻车。
在力扣LeetCode的动态规划入门题单里198. 打家劫舍几乎是每个人绕不开的第一道经典题。题目给了一排房屋每间房里有不同数额的现金但相邻的两间房连接着警报系统只要同一晚闯入两间相邻房屋就会触发报警要求算出在不惊动警察的前提下能偷到的最大金额。名字听起来有点戏剧化内核却非常干净从一个数组里选出一组不相邻的元素让它们的和最大。这道题在LeetCode热门100题里常驻也是面试里最高频的DP入门模型之一。刷透它你不只是会背一个转移方程而是真正理解“状态怎么定义、决策怎么转移、空间怎么压”这一整条DP解题链路。1. 题目拆解房子、警报与“相邻冲突”1.1 题目到底在说什么先看一个标准的测试用例nums [1, 2, 3, 1]输出是 4。为什么是 4因为你可以偷第 1 间1和第 3 间3结果 1 3 4。不能偷第 2 间2和第 3 间3因为它们是相邻的会触发警报。另一个示例[2, 7, 9, 3, 1]输出 12最优方案是偷 2、9、1加起来 12。这里要强调一个容易忽略的点题目说的是“不能偷相邻的两家”而不是“必须隔一家偷一家”。很多人一开始会误解成“要么偷奇数位要么偷偶数位”于是直接比较下标奇偶的和这肯定是错的。比如[3, 1, 1, 3]奇数位和是 3 1 4偶数位是 1 3 4但正确答案是偷第 1 间和第 4 间即 3 3 6。这说明最优选择在“隔不隔”这件事上很自由你必须让算法自己决策不能靠人工预设模式。所以题目的本质是给定一个非负整数数组从中选取一个子序列要求任意两个被选中的元素在原数组中不相邻使得选中元素的和最大。1.2 第一直觉为什么全都走不通拿到这种题正常人的第一个想法是枚举所有可能的偷法也就是每个房间都面临两个选择——偷或不偷于是总方案数是 2^n。当 n 100 时这个数字大得离谱暴力枚举在竞赛环境里直接超时。这就是为什么题目要求我们用更聪明的办法而不是硬算。那贪心行不行每次都选当前能选的最大金额举个反例[2, 1, 1, 2]。最大金额是 2如果先偷第 1 间2那第 2 间不能偷接下来能偷的是第 3 间或第 4 间偷第 4 间2总收益 4。可如果你一开始忍住不偷第 1 间直接偷第 2 间1和第 4 间2收益只有 3或者偷第 1 间2和第 4 间2收益 4。看起来贪心好像对了但换个例子[2, 1, 1, 3]贪心先偷 2剩下能偷的只有最后的 3总收益 5可实际上偷 1 3 4或者 2 3 5等等2 和 3 之间隔着 1 和 1不相邻所以 2 3 5 就是最优。还得继续找贪心失效的例子[3, 2, 2, 3]贪心先偷第 1 间 3剩下能偷第 3 间或第 4 间3 和第 4 间不相邻第 1 和第 4 不相邻所以偷 3 3 6。但最优其实是第 2 间 2 第 4 间 3 5不对第 1 间 3 第 4 间 3 6 更好。再找一个真正失效的[2, 3, 2, 3]贪心先偷第 2 间 3剩下只能偷第 4 间 3总共 6但偷第 1 间 2 第 3 间 2 4也不行。难点在于贪心没有全局视野它不知道当前这一个选择会对后面造成什么样的连锁反应。这就是动态规划登场的原因——把决策的过程记录下来让每个位置的最优决策都基于之前所有位置的最优结果。2. DP推演状态定义和转移方程是怎么来的2.1 核心认知dp[i] 表示“前 i 间房”能拿到的最大收益动态规划最重要的第一步不是写代码而是想清楚状态数组代表什么。对于打家劫舍最常见的定义是dp[i]表示从下标 0 到下标 i 的这 i1 间房里能偷到的最大金额。注意这个定义里包含一个非常关键的语义dp[i]并不要求第 i 间房一定要被偷。它只是说“如果我只能考虑前 i1 间房最好的结果是多少”。换句话说dp[i]已经替你做好了“偷第 i 间还是不偷”的取舍它存的是两者的最大值。为什么这个定义好用因为你写状态转移时不用再维护额外的标记不需要记住“上一次偷的是哪一间”。所有关于之前决策的信息都被压缩进了一个数字——前 i-1 间的最优值。这就是DP能取代暴力枚举的根本原因它把整个历史抽象成一个状态。2.2 转移方程推导偷还是不偷这是个问题假设现在轮到第 i 间房你要决定偷不偷它这件事只和两件事有关前 i-1 间房的最优结果以及前 i-2 间房的最优结果。如果你决定偷第 i 间房那么第 i-1 间房就绝对不能偷否则报警。所以在这种情况下你的收益是前 i-2 间房的最优收益加上nums[i]即dp[i-2] nums[i]。如果你决定不偷第 i 间房那么第 i-1 间房偷不偷都无所谓你直接继承前 i-1 间房的最优收益即dp[i-1]。最后取这两种决策里更大的那个得到状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])这里有一个初学者会很困惑的地方为什么不考虑“第 i-1 间没偷”的情况下偷第 i 间呢其实这个情况已经被上面的式子覆盖了。当dp[i-1]不偷第 i-1 间时它的值本身就可能来自于dp[i-2]或者更早的状态。而你偷第 i 间的收益是dp[i-2] nums[i]这个式子里已经包含了“前面怎么偷都行只要不碰第 i-1 间”的自由度。所以两种决策合并之后只剩下两个候选值不需要再细分。再往深一层想为什么dp[i]不需要依赖dp[i-3]、dp[i-4]因为约束只有一个“不能相邻”这是局部约束。dp[i-2]已经代表了下标 0 到 i-2 范围内的全局最优它内部必然已经妥善处理了所有相隔规则。因此当前决策只需要看最近的两个状态这也是后面能做空间压缩的根本依据。2.3 边界条件与初始化一件都不能漏有了转移方程还需要初始化。按数组下标来当数组为空返回 0。当只有一间房dp[0] nums[0]直接返回。当有两间房dp[1]应该等于max(nums[0], nums[1])因为两间相邻不能都偷所以只能选金额更大的那一间。有的同学会写dp[1] nums[1]这在数组两元素时其实也能过但如果nums[0] nums[1]比如[5, 1]你至少应该偷 5 而不是 1所以必须是max(nums[0], nums[1])这个初始化的本质是“前两间房的最优解”而不是“第二间房的值”。从i 2开始循环逐个计算dp[i]最后返回dp[n-1]。这就是最朴素的 O(n) 时间、O(n) 空间的版本。2.4 手动推演一遍看懂 dp 表的生长过程光看方程有点抽象拿官方示例[2, 7, 9, 3, 1]手动从头推一遍你就能直观感受到 dp 表是怎么“长”出来的inums[i]dp[i-2] nums[i]dp[i-1]dp[i]当前最优策略02--2偷第 0 间17--7偷第 1 间放弃第 0 间292 9 11711偷第 0 间和第 2 间337 3 101111维持之前的最优不偷第 3 间4111 1 121112偷第 2 间和第 4 间注意看 i3 这一行dp[3]比dp[2]没有增加因为偷第 3 间的话最多只能得到dp[1] nums[3] 7 3 10还不如不偷维持 11。这个例子完美展示了 dp 表“宁可不动也不乱动”的决策过程。最终dp[4] 12正好是题目的输出。整个过程你不需要回溯具体偷了哪些房间因为 dp 数组一路把最优值传递了下来。3. 空间优化从 O(n) 数组到两个滚动变量3.1 为什么 dp 数组有大量“废数据”看一遍转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你会发现计算dp[i]时只需要dp[i-1]和dp[i-2]至于dp[0]到dp[i-3]它们在后续计算中再也不会被用到。这就像你爬山的时候只需要知道当前位置和上一个台阶不需要记住十年前踩过的所有石头。所以开一个长度为 n 的数组完全是一种浪费。当 n 达到 10 的 5 次方甚至 10 的 6 次方时O(n) 的空间虽然也能过但在面试中面试官非常喜欢追问一句“能不能把空间复杂度降到 O(1)”。3.2 滚动数组写法的完整流程滚动数组的思路就是只保留最近两个状态用两个变量prev2和prev1分别充当dp[i-2]和dp[i-1]。初始化时prev2相当于dp[0]赋值为nums[0]。prev1相当于dp[1]赋值为max(nums[0], nums[1])。然后从i 2开始循环。每一轮cur max(prev1, prev2 nums[i]) prev2 prev1 prev1 cur循环结束后prev1就是整个数组的最优解。这个写法在力扣上性能表现非常好时间 O(n)空间 O(1)。这里要特别说明变量更新的顺序必须先取old prev1覆盖到prev2再把cur赋给prev1。如果你写反成prev1 cur prev2 prev1 # 此时 prev1 已经是 curprev2 拿到的是 cur不是真正的 dp[i-1]那下一轮计算时prev2 nums[i1]里用的就不是dp[i-1]而是dp[i]整个方程就错了。这个坑非常隐蔽跑小数组可能看不出来但一旦数据到位结果就会莫名其妙地偏大或偏小。3.3 滚动更新为什么安全一步步模拟给你看还是用[2, 7, 9, 3, 1]走一遍滚动数组初始prev2 2prev1 max(2, 7) 7i2cur max(7, 2 9) 11更新后prev2 7prev1 11i3cur max(11, 7 3) 11更新后prev2 11prev1 11i4cur max(11, 11 1) 12更新后prev2 11prev1 12返回prev1 12。可以看到滚动数组每一步算出的值和之前用完整 dp 数组推演的结果完全一致。因为它本质上只是把“数组”这个外衣脱掉了保留的仍然是同样的计算逻辑。这也是我推荐初学者先在纸上写 dp 数组版本、再改成滚动变量的原因——先把逻辑搞通优化只是形式上的改造。4. 三种语言的完整实现与刷题细节4.1 Python 实现最贴近思路的写法先给一个最容易理解的版本用 dp 数组def rob(nums): 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]这个版本思路直白适合写在注释里解释你的想法。如果你追求执行效率和极致空间直接上滚动数组版本def rob(nums): 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 prev1Python 的写法有一个天然优势列表索引不会越界因为if n 0和if n 1已经拦住所有异常情况。只要边界条件处理好这段代码在力扣上可以直接通过。4.2 Java / C 实现对比Java 和 C 在逻辑上与 Python 完全一致只有语法差异。Java 版本要注意判空否则输入为 null 时直接 NPEclass Solution { public int rob(int[] nums) { if (nums null || nums.length 0) return 0; int n nums.length; if (n 1) return nums[0]; int prev2 nums[0]; int prev1 Math.max(nums[0], nums[1]); for (int i 2; i n; i) { int cur Math.max(prev1, prev2 nums[i]); prev2 prev1; prev1 cur; } return prev1; } }C 版本用 vector本质上和 Java 是同一个思路class Solution { public: int rob(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint dp(n, 0); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] max(dp[i-1], dp[i-2] nums[i]); } return dp[n-1]; } };三种语言在力扣上跑同一个用例结果一致。我的建议是初学者先用 Python 把思路跑通再用 Java 或 C 写一遍因为这两种语言更接近面试手写代码的场景而且能逼你注意判空和越界等细节。4.3 提交时最容易踩的四个坑这道题通过率不低但我在力扣评论区见过很多失败的提交总结下来主要就这四个坑坑典型场景解决方案空数组没处理nums []开头加if n 0: return 0只有一个元素时访问 dp[1]nums [5]先判断if n 1: return nums[0]dp[1] 初始化为 nums[1] 而非 maxnums [5, 1]写成max(nums[0], nums[1])滚动变量更新顺序写反结果忽大忽小先算cur再prev2 prev1最后prev1 cur前两个坑本质是边界条件后两个坑本质是对 DP 语义的误解。我的习惯是写完代码先自己测三个用例空数组、一个元素、两个元素再测长数组。这种测试习惯能帮你省下很多无谓的提交失败。5. 一道题带出一串题变体与DP学习路线5.1 打家劫舍 II环形怎么拆这一题刷完之后下一步一定会遇到 213. 打家劫舍 II。它的变化是把房子排成一个环第一间和最后一间相邻所以你不能同时偷第一间和最后一间。破解的方法是把它拆成两个不环形的问题一个是“不偷第一间”即考虑nums[1:]另一个是“不偷最后一间”即考虑nums[:-1]。分别对这两个数组跑 198 的解法最后取最大值。为什么能这么拆因为环形带来的额外约束只有一个首尾不能同时被偷。那我们就分情况讨论——要么不偷首要么不偷尾这两种情况覆盖了所有合法方案而且每种情况下剩下的房子又变回了线性排列。这就是 DP 中的一个重要技巧把新约束拆成互斥情况逐一击破。5.2 打家劫舍 III二叉树和树形DP再升级一档是 337. 打家劫舍 III房子变成了一棵二叉树父子节点不能同时被偷。这时线性 DP 的数组结构改成树形 DP但决策模型完全一样。每个节点返回两个值偷当前节点的最大收益和不偷当前节点的最大收益然后自底向上合并。def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) # 偷当前节点左右孩子都不能偷 rob_cur node.val left[1] right[1] # 不偷当前节点左右孩子各自取最优 not_rob_cur max(left) max(right) return (rob_cur, not_rob_cur) return max(dfs(root))这个版本的代码很短但背后是标准的树形 DP 思维。当你把 198、213、337 三题连在一起刷完之后会发现它们共享同一个决策模型“当前节点选或不选子问题的最优解怎么组合”。这也是力扣热门 100 题里 DP 板块最喜欢考的类型之一。5.3 DP刷题的建议路线与判断技巧如果你刚开始刷动态规划不要把 198 当成一道题把它当成一个模板。我建议的刷题路线是先刷 198 打家劫舍理解“选/不选”的决策模型能独立推导出转移方程。再刷 70 爬楼梯和 121 买卖股票的最佳时机这俩同样是一维 DP状态定义和转移相对简单可以巩固基本功。之后刷 322 零钱兑换和 300 最长递增子序列这俩开始涉及“对每个状态遍历所有决策”是从一维 DP 向多维 DP 过渡的桥梁。回头再看 213 和 337体会同一个模型在不同数据结构上的变形。判断一道题该不该用 DP就看两个特征一是存在重叠子问题也就是递归解决时同一个状态被反复计算二是具有最优子结构即全局最优总能由子问题的最优组合而成。打家劫舍正好两者都满足所以它才能成为经典中的经典。学到这里你已经掌握了打家劫舍这道题从暴力到 DP 再到空间优化的完整进化路径。我个人在实际刷题中的体会是这题真正的分水岭不在转移方程而在你能不能想清楚“dp[i] 代表前 i 间房的最优值而不是第 i 间房必须偷的值”。想明白这一点后面 213、337 甚至更多变体都会顺畅很多。最后分享一个我自己的小习惯做任何 DP 题先写一行注释把状态定义写清楚再动键盘。状态定义写不出来的题代码写得再漂亮也容易在边界上翻车。
