Hot 100 系列里198. 打家劫舍House Robber是我遇到频率极高的一道题也是很多刷题攻略公认的“动态规划入门第二题”——第一题通常是爬楼梯。题目本身是一个生活化的小故事一条街上有一排房屋每间房放着不同数量的现金但相邻两间房在同一晚上被偷会触发防盗系统报警所以不能连着偷问在不触发警报的前提下最多能偷到多少钱。这道题最妙的地方在于它把“相邻约束”包装成了一个看似简单的数组问题但背后串联起了暴力递归、重叠子问题、记忆化搜索、自底向上动态规划、滚动数组空间优化这一整条算法演进路径。我在面试 mock 和带新人刷题时经常拿它做切入点因为只要把这一题吃透后面遇到 213. 打家劫舍 II、337. 打家劫舍 III 甚至 740. 删除并获得点数都能顺藤摸瓜地串起来。这篇就把我从最初解法到最优解再到系列扩展题的完整思考过程写出来。1. 这道题在 Hot 100 里的地位与题意拆解1.1 题目到底在问什么先过一遍题面。你有一个非负整数数组numsnums[i]表示第i间房屋里存放的现金金额。现在你要选择若干间房屋去偷约束条件是不能偷相邻的两间。目标是让偷到的总金额最大。举个例子nums [1, 2, 3, 1]最优选择是偷下标 0 的 1 和下标 2 的 3总金额 4。注意下标 0 和下标 2 中间隔了一个下标 1所以不算相邻可以同时偷。而nums [2, 7, 9, 3, 1]最优是 2 9 1 12对应下标 0、2、4也就是隔一个偷一个。题目数据范围一般到数组长度n 100每个金额都是非负整数。这个数据范围其实暴露了一个关键信息如果你第一时间想到暴力枚举所有“偷/不偷”的组合那 2 的 n 次方种方案在 n 100 时是天文数字跑都跑不完。所以这道题真正的核心在于能不能在 O(n) 时间内计算出一个全局最优的组合而不是罗列所有可能性。我第一次做这道题的时候其实纠结了很久“到底要怎么保证我选出来的组合是最大的”后来才意识到这本质上是一个最优子结构问题——我只需要关心“看到第 i 间房为止最多能拿多少钱”后面的决策完全可以通过这个信息递推出来。这个视角的转变是我理解动态规划的起点。1.2 为什么必须用动态规划贪心的死胡同很多人拿到这种“选与不选 相邻约束”的题目第一反应是贪心每次挑当前可偷的最大金额拿完就把邻居划掉然后再继续挑。听着挺合理我给你一个反例nums [5, 4, 100, 4, 5]。按贪心思路先找金额最大的房屋是下标 2 的 100。偷了它之后相邻的下标 1 和下标 3 就不能再偷了。剩下可选的是下标 0 的 5 和下标 4 的 5你只能再挑一个最多再拿 5总金额 100 5 105。但最优解是多少偷下标 0 的 5、下标 2 的 100、下标 4 的 5这三个位置两两不相邻总金额 110。贪心因为过早锁定了中间的 100反而损失了左右两头的收益。这个例子说明了一个核心问题在打家劫舍这种约束下当前的选择会通过“相邻禁止”影响后续很多房屋的可选集合局部最优点并不能可靠地推出全局最优。也就是说贪心缺少证明很容易找到反例。而动态规划不同它把“到第 i 间为止的最优值”完整地存下来再做状态转移时已经把“偷”与“不偷”两条路径的最大值都考虑清楚了每一步都有严格的数学依据。那为什么不直接用带剪枝的回溯搜索回溯当然能得到正确答案但每个状态的分支是指数级的在 n 达到 100 时无法承受。更重要的是回溯过程中大量子问题是重复的——比如“前 3 间的最优值”会从好几个不同的递归路径里被反复计算。动态规划的本质就是把这些重复子问题缓存起来用空间换时间把指数级降到线性级。这也是我在下面要重点展开的内容。2. 从暴力递归到状态定义这个 DP 是怎么一步步想出来的2.1 先写出最直觉的暴力递归版本我自己刷题有一个习惯拿到一道不熟悉的 DP 题不急着直接套模板而是先写一版暴力的递归搜索把“决策过程”想清楚。对于打家劫舍可以定义一个函数dfs(i)表示从下标 0 到下标 i 的这些房屋中能偷到的最大金额。那么到了第 i 间房只有两种决策不偷第 i 间那第 i-1 间不受影响答案等于dfs(i-1)。偷第 i 间第 i-1 间必须跳过因为相邻不能偷答案等于dfs(i-2) nums[i]。取这两种决策的较大值就得到了递推关系dfs(i) max(dfs(i-1), dfs(i-2) nums[i])递归出口也很简单i 0时没有房屋可偷返回 0i 0时只有一间房返回nums[0]。def rob(nums): n len(nums) def dfs(i): if i 0: return 0 if i 0: return nums[0] return max(dfs(i - 1), dfs(i - 2) nums[i]) return dfs(n - 1)这段代码逻辑完全正确但性能非常差。dfs(i)会递归调用dfs(i-1)和dfs(i-2)而这两个调用各自又会继续分裂整棵递归树几乎是满二叉树时间复杂度是 O(2^n)。n 100 时这个计算量完全不可行。我拿 n 5 画过这棵递归树dfs(3)会被dfs(4)和dfs(5)两条路径反复计算很多子问题其实只有 n 个却被重复算了无数次。2.2 记忆化搜索把重复计算缓存起来递归树里那些重复的子问题用缓存就能解决。加一个 memo 数组记录每个dfs(i)的结果第二次遇到就直接返回。def rob(nums): n len(nums) memo [-1] * n def dfs(i): if i 0: return 0 if i 0: return nums[0] if memo[i] ! -1: return memo[i] memo[i] max(dfs(i - 1), dfs(i - 2) nums[i]) return memo[i] return dfs(n - 1)这样每个下标 i 只计算一次时间复杂度降到 O(n)。这就是自顶向下的动态规划也叫记忆化搜索本质上是“递归 缓存”。虽然已经能 AC 了但递归调用有函数栈开销而且代码模板在不同题目里不太统一所以我一般只拿它来辅助思考真正写进代码的通常是自底向上的递推版本。这里有一个值得记住的观点记忆化搜索和 DP 其实是同一个东西只是计算顺序不同。一个从大的子问题出发递归地依赖小的子问题一个从小子问题开始一点点拼出大的子问题。理解了这个你就不会被“DP 到底要几重循环”这样的问题困住因为你已经知道状态之间的依赖关系了。2.3 自底向上的 DP把递归改成填表自底向上的写法更符合大多数人对 DP 的认知定义一个dp数组dp[i]表示下标 0 到 i 范围内能偷到的最大金额然后从小往大填。状态转移方程和递归版本完全一致dp[i] max(dp[i-1], dp[i-2] nums[i])初始化要注意两点dp[0] nums[0]因为只有一间房时只能偷它。dp[1] max(nums[0], nums[1])两间房不能同时偷取金额更大的那间。def rob(nums): if not nums: return 0 n len(nums) 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[n - 1]你也可以换一种状态定义dp[i]表示**前 i 间房下标 0 到 i-1**能偷到的最大金额那么dp[0] 0dp[1] nums[0]递推时用nums[i-1]。两种方式没有本质区别只是下标偏移。但我个人更推荐“dp[i] 表示前 i 间”的写法因为它的边界更统一处理空数组时也更自然。不过面试中两种都有人写关键是别把下标弄混。自底向上的 DP 时间复杂度 O(n)空间复杂度 O(n)。到这里已经是一份标准的合格答案了但面试官一般还会追问一句“能不能把空间优化到 O(1)”这就是下一节要讲的内容。3. 空间优化与最常用的滚动数组写法3.1 为什么可以压成 O(1)观察上面的状态转移方程dp[i]只依赖dp[i-1]和dp[i-2]。也就是说在计算当前状态时我们完全不需要整个 dp 数组只需要知道前两个值就够了。这就像记账的时候你只需要记住“上上个月”和“上个月”的结余就能算出这个月的结余。这种优化思路叫滚动数组或者叫状态压缩。数据库里那种“窗口函数”也是类似的思想——永远只关心滑动窗口里的几个关键值。把 dp 数组换成两个变量空间复杂度直接从 O(n) 降到 O(1)。3.2 两套常用模板选一套顺手的使用我最常用的是一套“双变量滚动”模板代码非常简洁而且能自然处理数组长度小于 2 的情况def rob(nums): prev 0 # 代表 dp[i-2] cur 0 # 代表 dp[i-1] for num in nums: # 偷当前房屋: prev num # 不偷当前房屋: cur nxt max(cur, prev num) prev cur cur nxt return cur这段代码的初值设置很巧妙prev 0, cur 0表示还没有处理任何房屋时“上两间房的收益”和“上一间房的收益”都是 0。第一次迭代时nxt max(0, 0 nums[0]) nums[0]相当于 dp[0]第二次迭代时nxt max(nums[0], 0 nums[1])正好是两间房取最大值。所以这个模板不需要单独处理长度为 0 或 1 的边界这是我很喜欢它的原因。另外一套是显式的三变量写法思路更直观也适合在面试时讲给面试官听def rob(nums): if not nums: return 0 n len(nums) 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两套代码的最终结果完全一样。区别在于双变量模板更精练但初值的含义要靠prev和cur的滚动语义来理解三变量模板的变量名prev2、prev1、cur直接对应 dp 状态讲起来更好懂。如果你在刷题初期两套都写几遍加深理解如果已经熟练了选一套固定成自己的肌肉记忆就够了。3.3 边界条件与更新顺序的坑这个题的 AC 代码看起来很简单但实际提交时出问题最多的恰恰是边界和变量更新顺序。第一个坑是长度为 1 的情况。如果用三变量模板n 1时访问nums[1]会越界所以必须先特判。双变量模板没有这个烦恼但代价是你要理解它那个“凭空多出来的 0 号状态”。第二个坑是滚动更新的顺序。假设你这么写prev cur cur max(cur, prev num)注意看第二行里的prev已经被上一行改掉了它不再是“上上个状态”了结果就全错了。正确写法应该先把max(cur, prev num)算出来再统一更新或者利用 Python 的元组同时赋值prev, cur cur, max(cur, prev num)Python 的元组赋值会先同时计算右边表达式的值再依次赋值所以这种写法是安全的。其他语言里建议用临时变量缓存。第三个坑是初始化混淆。cur到底是 dp[i-1] 还是 dp[i]不同模板语义不同。如果不理解就硬套模板很容易在二分、环形变体等题目里翻车。我自己就因为在 213 题里直接把环形拆成两段再用双变量模板时没想清楚prev、cur的初始值卡了快半小时。所以强烈建议模板可以背但必须知道每个变量在任意时刻代表什么。4. 一道题带出一个系列198 的兄弟们刷题最过瘾的时刻就是发现一道题能串起一大堆题目。打家劫舍系列就是这样198 只是开胃菜后面还有环形版本、树形版本以及一个看似无关但本质完全同构的题目。4.1 213. 打家劫舍 II环形数组拆成两段线性问题213 题把房屋排成了一个环第一间房和最后一间房相邻。这个改动带来了一个新约束首尾不能同时被偷。那最优解只可能出现在两个范围内偷第 0 到第 n-2 间不偷最后一间偷第 1 到第 n-1 间不偷第一间把这两个范围的线性打家劫舍结果取最大值就是环形问题的答案。注意n 1时要特判因为两个区间都为空或者只有一个元素时要直接返回nums[0]。def rob(nums): if len(nums) 1: return nums[0] def rob_range(nums): prev, cur 0, 0 for num in nums: prev, cur cur, max(cur, prev num) return cur return max(rob_range(nums[1:]), rob_range(nums[:-1]))理解这个拆环的关键在于最优解中首和尾不可能同时出现所以它必然被“不偷首”和“不偷尾”两个集合中的一个覆盖。这种“碰到环就拆成两个线性问题”的思路在很多题目里都通用比如环形数组的最大子数组和。拆环的逻辑想通了代码反而是最机械的部分。4.2 337. 打家劫舍 III树形 DP 二元组模板再升级一步房屋变成了一棵二叉树父子节点不能同时偷。这不就变成了树形 DP 吗树上的状态转移天然适合后序遍历因为子节点的信息要先计算完才能归并给父节点。每个节点需要返回两个值rob_node偷当前节点时子树能获得的最大金额等于node.val 左子树不偷的最大值 右子树不偷的最大值not_rob_node不偷当前节点时子树能获得的最大金额等于max(左子树偷或不偷) max(右子树偷或不偷)用 Python 的元组来装这两个值这是树形 DP 里非常经典的模板def rob(root): def dfs(node): if not node: return (0, 0) left dfs(node.left) right dfs(node.right) rob_node node.val left[1] right[1] not_rob_node max(left) max(right) return (rob_node, not_rob_node) return max(dfs(root))我看过很多同学第一次接触这题时想着用“隔层偷”的方式去层序遍历其实行不通。树形 DP 的正解就是让每个节点自己汇报“我在场”和“我不在场”的收益父节点根据子节点的汇报做决策。这种返回二元组的写法几乎可以原封不动地套用到别的树形 DP 题里比如树的独立集、监控二叉树之类的非常值得存进自己的模板库。4.3 740. 删除并获得点数发现同构直接转化如果说 213 和 337 是 198 的兄弟那 740. 删除并获得点数就是一个“长得完全不一样”的双胞胎。题目说的是每次选一个数字 x 并获得 x 分但要删除所有 x-1 和 x1 的点数。翻译一下你拿了数字 x就不能再拿 x-1 和 x1。这不就是打家劫舍吗先把原始数组映射到“值域数组”上count[x] x 出现的次数 * x表示某个数值如果被选它能带来的总分数。然后你会发现数值 x 和 x1 之间存在“相邻禁止”的约束和房屋相邻不能偷完全一致。于是直接套线性 DPdef delete_and_earn(nums): if not nums: return 0 max_val max(nums) points [0] * (max_val 1) for num in nums: points[num] num prev, cur 0, 0 for point in points: prev, cur cur, max(cur, prev point) return cur这道题的启发意义很大。刷题时经常遇到“表面不同、本质相同”的题打家劫舍的“相邻不能选”约束散落在很多题目里。学会把不熟悉的题抽象成熟悉的状态转移是提升刷题效率的一个关键能力。5. 刷题与面试的实战心得常见坑与扩展思路5.1 快速识别线性 DP 的思考路径回头总结一下识别这类线性 DP 有固定的思考路径。第一步确认决策方式每个位置都存在“选”或“不选”的二元选择。第二步检查决策约束选择当前元素会禁止邻居这就是典型的“带冲突的最优化问题”。第三步尝试定义状态dp[i]表示“处理到第 i 个位置时满足约束的最优结果”然后模拟“选”和“不选”两种可能的转移谁大留谁。这套路径几乎可以直接套用到最长递增子序列、最大子数组和、股票买卖系列等题目上。区别只在于状态定义和相邻依赖的范围打家劫舍依赖前两个状态i-1 和 i-2所以是一维滚动最长递增子序列可能要依赖之前所有状态复杂度就上到 O(n^2)如果依赖二维关系那就是二维 DP 或区间 DP。所以一次次说“DP 靠刷题找感觉”其实核心是不断积累“状态 转移”的识别模式。日常刷题时我喜欢在纸上先把递归版本写出来再标出重复子问题再优化到滚动数组。这个过程基本上能覆盖 80% 的简单和中等题。5.2 面试官最常问的 follow-up这道题的代码很短面试官一般不会满足于“AC 就完了”通常会顺着追问下面几个问题为什么不能用贪心用我前面给过的反例[5, 4, 100, 4, 5]回答核心观点是“当前决策会影响后续多个选择”。空间复杂度能优化吗引出滚动数组讲清楚 dp[i] 只依赖 dp[i-1] 和 dp[i-2]。如果要输出偷了哪几间房怎么改维护一个choice[i]数组记录每个 i 是在“偷第 i 间”还是“不偷第 i 间”的决策下得到最优解的最后从尾部回溯。这个 follow-up 很考验对状态转移的掌握。如果金额出现负数呢题目保证非负整数所以初始化为 0 是安全的若允许负数dp[i]的初始值要设为负无穷因为“不偷”的收益是 0不能直接用 0 参与 max 比较。数组特别长怎么办在线性递推中空间 O(1) 已经最优时间 O(n) 也是必须的下界因为每个元素至少要读一次。如果能在面试里把这些问题都答出来这题的区分度就完全体现出来了。5.3 常见 bug 速查表下面整理几个我在刷题和帮别人 review 时遇到的典型 bug直接做成表格方便对照自查。错误现象可能原因修复方法数组长度为 1 时越界直接访问 nums[1] 初始化 dp[1]提前特判 n 1或改用双变量模板结果偏大/偏小逻辑错乱状态转移方程里混用了 dp[i-1] 和 dp[i-2] 的语义先明确 dp[i] 是“前 i 间”还是“到第 i 间”全篇统一滚动数组结果错乱更新 prev 和 cur 的顺序颠倒用临时变量缓存旧值或利用元组同时赋值环形版本结果不对没有处理 n 1 特判环形拆两段时先判断单元素情况贪心结果在某些样例下错误使用了“每次取最大”的贪心策略换用 DP并理解状态转移的正确性来源提示如果你用“双变量模板”写 198 题发现结果不对劲第一件事检查循环里prev和cur的赋值顺序第二件事检查nums的遍历是否把每个元素都用了一次。这两条能解决我见过的大部分模板错位问题。最后再分享一个我自己的小习惯每次刷到一道新 DP 题我会先写一个“最小可运行版本”也就是能过样例、思路完整但可能空间不是最优的写法跑通之后再优化到滚动数组。这样一旦优化过程中出现 bug至少能回到正确版本重新对照。打家劫舍这道题我前前后后刷了不下五遍但每一遍仍能在“讲给面试官听”这个层面发现新的表达角度。它值得你多花时间琢磨因为这道题的思考方式会跟着你一直延伸到背包、树形 DP、状态压缩这些更复杂的题型里。