如果你在刷 LeetCode 热门 100 题大概率会在前五十题里撞上这道 198. 打家劫舍。它被标记为中等难度但代码量少得让很多人怀疑是不是标错了——AC 代码算上函数签名也就十几行。可偏偏就是这么一道小题目翻车率一点都不低。我见过有人初始化就写错有人一维 DP 公式背下来了换个环形的打家劫舍 II 就完全不知道从哪下手也见过有人把它当简单题跳过结果在面试里被面试官一路追问到树形 DP当场卡住。这道题真正的价值不在 AC 本身而在于它是动态规划入门的一道枢纽题状态定义、递推推导、边界处理、空间优化四个 DP 核心考点全部覆盖。它还是 LeetCode 整个打家劫舍系列的地基从 198 到 213、337、2560每个变体都是在它基础上加了环、加了树、加了二分答案。甚至很多周赛题目剥掉包装之后核心还是这个模型。本文不打算只贴一份题解而是把从暴力递归到空间优化、再到系列变体的完整推导链条走一遍顺便聊聊我在面试和刷题中反复踩过、也反复被人问过的一些坑。1. 一道简单的中等题题目咬文嚼字与热门题地位1.1 题目到底在说什么先把原题描述搬出来你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下一夜之内能够偷窃到的最高金额。给出两个标准示例nums [1,2,3,1]答案是 4偷第 1 间和第 3 间即1 3。nums [2,7,9,3,1]答案是 12偷第 1、3、5 间即2 9 1。第一个示例看起来像是隔一个偷一个容易让人形成思维定势第二个示例则直接打破了这个定势。如果再仔细推敲最优偷法也不一定是从第一间开始跳着偷比如[2,1,1,2]最优是偷两头2 2 4中间两间直接跳过。这说明题目不是简单的奇偶选择而是一个真正的决策问题。题目里有个容易被忽略的关键词非负整数数组。这意味着所有金额都不小于 00 元房屋在逻辑上是允许的。这个约束在后面的二分答案变体里很重要因为金额的下界是明确的 0。1.2 为什么它在热门 100 题里这么靠前热门 100 题承担的任务是用尽量少的前置知识展示尽量核心的算法范式。198 题完美符合这个要求不需要任何数据结构基础不需要理解图论概念只需要一个数组和一个递推关系就能把动态规划状态、转移、边界、优化这套思维完整地过一遍。从题库体系的纵向看它是整个打家劫舍系列的源头。LeetCode 官方沿着这道题分别设计了环形的 213、树形的 337、以及结合二分答案的 2560一个比一个进阶。很多时候周赛题目也是从这类经典模型上生长出来的所谓母题就是这种题。这也是为什么它能在周赛题解、热门题单里反复出现——它够基础、够经典、够有扩展性。我记得第一次刷这道题时以为记住dp[i] max(dp[i-1], dp[i-2] nums[i])就完事了。后来才发现真正难的不是公式本身而是清楚这个公式是怎么来的、为什么边界要那样初始化、为什么空间可以优化到 O(1)。接下来这部分就是完整的推导过程。2. 从暴力递归到动态规划状态定义是怎么一步步逼出来的2.1 一张纸推导暴力递归先把题目转化成更形式化的说法从数组里选一些位置任意两个被选位置的下标差至少为 2目标是被选位置上的值之和最大。最朴素的想法是枚举所有选择方案每个房屋都有偷和不偷两种选择然后筛掉相邻的再比较和的大小。方案数是指数级的数组长度一旦超过 30 基本就跑不动了。这个思路虽然朴素但它暗示了一件事这题天然适合用选或不选的视角建模。把问题定义成函数f(i)考虑前 i 个房屋下标 0 到 i能偷到的最大金额。对于第 i 个房屋只有两种互斥情况不偷它那么最优解就是前 i-1 个房屋的最优解f(i-1)。偷它那么第 i-1 个房屋必须跳过再加上前 i-2 个房屋的最优解f(i-2) nums[i]。两种情况取最大值就得到了递推公式f(i) max(f(i-1), f(i-2) nums[i])这里要特别注意这个 max 不是选当前这间还是选前两间这种局部比较而是偷第 i 间带来的完整方案和不偷第 i 间保留前 i-1 间的最优方案这两个完整方案之间的取舍。很多新手把递推理解成决策当前这一间结果越想越绕。想清楚这两者是完整方案之间的比较整道题就通了一半。2.2 重叠子问题为什么暴力递归会超时有了递推公式很多人第一反应是用递归直接实现一提交就超时。原因在于重复计算。画一下递归展开的样子要算f(5)需要f(4)和f(3)算f(4)需要f(3)和f(2)算f(3)需要f(2)和f(1)。也就是说f(3)被f(5)和f(4)各自需要一次下面更小的子问题被重复计算的次数更多。整棵递归树的节点数是指数级的数组长度到 50 以上就不可接受了。这类问题的特征就叫重叠子问题大问题拆开后很多小问题反复出现。动态规划的核心洞察是既然子问题会反复出现那就花一点空间把它们存起来第一次算完记下来下一次直接用。这就是记忆化搜索也叫自顶向下的动态规划。用 Python 写就是def rob(nums): n len(nums) memo [-1] * n def dfs(i): if i 0: return 0 if memo[i] ! -1: return memo[i] res max(dfs(i - 1), dfs(i - 2) nums[i]) memo[i] res return res return dfs(n - 1)到这里时间复杂度已经降到了 O(n)因为每个f(i)只算一次。但递归栈会占额外空间而且memo[i] ! -1这个判断依赖金额非负的性质——如果金额可能为负数这种标记方式就需要改。虽然这版已经能过题但推导还没结束。2.3 从记忆化到自底向上的递推记忆化搜索是从大问题出发递归到最小子问题再一路逐步返回。反过来想既然最小子问题的答案是可以直接确定的为什么不让循环从最小的子问题开始一路推到最大的问题这就是自底向上的动态规划也是大家最熟悉的dp数组写法。最小子问题是什么没有房屋答案是 0只有一个房屋答案就是它本身只有两个房屋答案取两者中的较大值。于是初始化就确定了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[n - 1]dp[i]的含义和f(i)完全一样前 i 个房屋能偷到的最大金额。递推公式一字不差只是计算方向从从大往小递归变成了从小往大循环。这两种写法本质上是一回事区别只在于代码执行方向。面试时如果时间紧张直接从这版开始写完全没问题但最好心里清楚它和递归版本的关系因为面试官很可能追问。3. 递推公式里的暗坑以及边界条件的三个角落3.1 dp[1] 的初始化为什么不能写成 nums[1]这是我见过翻车率最高的地方。很多人在dp[1] max(dp[0], dp[1])这一步掉链子直接写成dp[1] nums[1]或者dp [nums[0], nums[1]]。当nums[0] nums[1]时这个初始化就把最优子结构算错了后面所有结果都会被污染。举个反例nums [5, 2, 1, 3]。只看前两个房屋当然偷 5 比偷 2 赚所以dp[1]应该是 5 而不是 2。如果初始化成 2递推到i2时dp[2] max(dp[1], dp[0] nums[2]) max(2, 5 1) 6看起来这步还能歪打正着算出 6但再往下递推错误的dp[1]会持续影响后面的状态最终答案大概率是错的。正确写法是dp[1] max(nums[0], nums[1])这个初始化的语义是前两个房屋只能偷其中一间那当然选金额大的那间。3.2 空数组、单元素数组与循环起点边界条件在 DP 里从来不是凑出来的而是被测问题的最小规模决定的。n 0没有房屋返回 0。n 1只偷这一间返回nums[0]。n 2两间只能偷一间返回max(nums[0], nums[1])。官方题解里其实允许nums.length 1空数组不见得会出现在测试用例里但在面试中把n 0这个分支写出来会显得你考虑问题全面。更重要的是后面打家劫舍 II 在拆分环形数组时会把数组切成两个子区间其中一个子区间有可能是空的所以这个边界分支直接决定了辅助函数能不能复用。循环起点从i 2开始也对应最小子问题的规模前两个房屋已经处理完了第三个房屋下标 2才开始享受完整的递推公式。如果n正好是 2循环一次都不用进直接返回dp[1]即可。3.3 一维 DP 与二维 0/1 状态写法的等价性有些题解会写成二维状态def rob(nums): n len(nums) dp [[0, 0] for _ in range(n)] dp[0][0] 0 dp[0][1] nums[0] for i in range(1, n): dp[i][0] max(dp[i - 1][0], dp[i - 1][1]) dp[i][1] dp[i - 1][0] nums[i] return max(dp[n - 1][0], dp[n - 1][1])这里dp[i][0]表示不偷第 i 间dp[i][1]表示偷第 i 间。不偷当前房屋时上一间偷不偷都行所以是max(dp[i-1][0], dp[i-1][1])偷当前房屋时上一间必须没偷所以只能是dp[i-1][0] nums[i]。两种写法都能 AC一维写法代码更短二维写法的状态语义更完整也更像后面树形 DP 的雏形。我个人的建议是面试时先讲二维版本因为它把约束条件如何体现在状态转移里展示得更直观然后再现场化简成一维版本观众能很清楚看到你的思考过程。4. 空间优化到 O(1)滚动变量背后的状态依赖分析4.1 为什么可以滚动观察一维递推公式dp[i] max(dp[i-1], dp[i-2] nums[i])。每一步只用到dp[i-1]和dp[i-2]更早的状态在算完当前值之后就没用了。这就好比你爬楼梯手里只需要记住上一级和上上一级的数字就能算出下一级不需要把第 1 级到第 n-2 级所有数字都背在身上。理论上甚至可以把 dp 数组的长度从 n 缩短到常数。这种优化叫滚动数组是空间优化的常见手段。它不改变递推公式本身只是把不再需要的历史状态及时丢弃。4.2 代码实现与赋值顺序的坑经典的 O(1) 空间版本长这样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和prev1都初始化为 0这样不需要显式处理空数组和单元素数组。第一个元素进来时prev2扮演第 -1 个房屋的兜底值cur max(0, 0 nums[0]) nums[0]正好等价于dp[0] nums[0]。最大的坑在赋值顺序。假如写成prev2 prev1 prev1 max(prev1, prev2 num)那就彻底错了。因为在算第二个式子时prev2已经被覆盖成prev1的旧值你再也拿不到真正的上上一个值。Python 的prev2, prev1 prev1, cur之所以安全是因为等号右侧先整体求值再统一赋值天然避免了顺序问题。数组长度较大时这种错误不容易被小数据暴露一旦隐藏起来特别难查。4.3 复杂度分析的准确说法放在面试场景下代码写完后要闭嘴反思两秒把复杂度讲清楚时间复杂度 O(n)因为只需要遍历一次数组空间复杂度 O(1)因为只用了两个变量。关于能不能继续优化这个问题正确的答案是不能。读入整个数组本身就需要 O(n)而相邻约束又意味着每个房屋至少要被比较一次所以时间和空间都已经达到输入规模下的下限。能说出这一层面试官会比较满意。5. 一道 198牵出整个打家劫舍家族5.1 打家劫舍 II环状数组的破环思路213 题把房屋排成一个环首尾相连。多出来的约束只有一个第一个房屋和最后一个房屋不能同时偷。解决方法不是直接改递推而是做分类讨论。任意一个合法偷法要么没有偷第一个房屋那么它的范围等同于nums[1:]要么没有偷最后一个房屋相当于范围nums[:-1]。这两种情况的并集覆盖了所有合法方案所以答案是两种情况的最大值。def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] def rob_range(l, r): prev2 prev1 0 for i in range(l, r 1): cur max(prev1, prev2 nums[i]) prev2, prev1 prev1, cur return prev1 return max(rob_range(0, len(nums) - 2), rob_range(1, len(nums) - 1))注意这里rob_range接收左右下标而不是切片是为了避免每次复制数组产生额外 O(n) 空间。我觉得这个细节值得强调很多人图省事直接传nums[:-1]和nums[1:]代码没错但空间复杂度从 O(1) 悄悄变成了 O(n)在面试里会被追问。5.2 打家劫舍 III树形 DP 的入门337 题直接换了个数据结构房屋变成一棵二叉树父节点和子节点不能同时偷。这个时候一维 DP 不够用了得用 0/1 状态在树上做后序遍历。每个节点返回一个二元组分别表示不偷当前节点和偷当前节点的最大收益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[0] right[0] # 不偷当前节点左右孩子各自取最大值 not_rob_cur max(left) max(right) return (not_rob_cur, rob_cur) return max(dfs(root))这个写法和前面二维 DP 版本的对应关系非常直接dfs(node)相当于dp[node][0]和dp[node][1]。叶子节点返回(0, val)空节点返回(0, 0)都是最小子问题的自然定义。这一题是树形 DP 的经典入门题刷完它之后再去做树上最大独立集类的问题会轻松很多。5.3 打家劫舍 IV二分答案 贪心判定2560 题的包装更有意思给定数组和整数 k定义能力值为一次偷窃中偷到的房屋金额的最大值现在要求偷至少 k 个房屋问最小能力值是多少。这类最小化最大值的表述是二分答案的标志性信号。直接想怎么偷很难但反过来问就简单了如果我告诉你能力值是 cap那么能偷到至少 k 间吗判定函数可以贪心从左到右扫描遇到金额小于等于 cap 的房屋就偷然后跳过下一间否则跳过当前房屋。这样做是正确的因为在选择可偷房屋时能偷就偷不会让后续可选项变差只会把约束往前挤占一间属于最优策略。def minCapability(nums, k): def can(cap): cnt 0 i 0 n len(nums) while i n: if nums[i] cap: cnt 1 i 2 else: i 1 return cnt k lo, hi 0, max(nums) while lo hi: mid (lo hi) // 2 if can(mid): hi mid else: lo mid 1 return lo二分范围是 0 到数组最大值判断函数是 O(n)总体复杂度 O(n log max(nums))。如果刷过 LeetCode 875 爱吃香蕉的狒狒会发现判断函数的设计手法如出一辙给定一个能力参数写一个朴素的模拟函数判断可行性再二分搜索最小的可行参数。这不是巧合二分答案类题目很多都是这个套路。5.4 系列变体对比把四条题目放在一起看脉络非常清晰题目数据形态核心技巧复杂度198 打家劫舍线性数组一维线性 DPO(n) 时间O(1) 空间213 打家劫舍 II环形数组破环成两个线性问题O(n) 时间O(1) 空间337 打家劫舍 III二叉树后序遍历 0/1 状态O(n) 时间O(h) 栈空间2560 打家劫舍 IV线性数组 k二分答案 贪心判定O(n log max) 时间O(1) 空间每一道都是在上一道基础上加了一个新维度。线性 DP 是底座环形考的是分类讨论树形考的是状态表达二分答案考的是从另一个方向思考问题。把这四题连起来刷一遍比单独刷十道零散 DP 题的效果好很多。6. 面试实战如何把这道题讲成加分项6.1 面试官真正想听的分析过程这道题如果出现在面试里最忌讳的就是题目读完直接甩出一行dp[i] max(dp[i-1], dp[i-2] nums[i])。面试官想看的是你的推导链条而不是背诵能力。我在模拟面试中常用的口述模板是我先从暴力递归开始想。定义 f(i) 为前 i 个房屋的最大收益那么 f(i) 只有两种情况要么不偷第 i 间答案就是 f(i-1)要么偷第 i 间那么第 i-1 间必须跳过答案是 f(i-2) nums[i]。取最大值。这个递归有大量重叠子问题所以可以用数组缓存这就是记忆化搜索。然后我把它改成自底向上的递推初始化 dp[0] 和 dp[1] 分别是 nums[0] 和 max(nums[0], nums[1])循环从左到右填表。最后观察递推只依赖前两个值所以用两个滚动变量把空间压到 O(1)。这段话信息量很足但自然讲出来只需要一两分钟。重点是每个环节之间有因果推动暴力递归超时所以引入记忆化递归栈有额外开销所以改成自底向上填表只依赖前两个值所以滚动优化。这个链条本身就是面试官想看到的分析能力。6.2 三个高频追问与标准应答追问一如果房屋围成一个环怎么办应答要点是第一个和最后一个不能同时偷因此把问题拆成不偷第一个和不偷最后一个两个子问题分别跑线性 DP取最大值。一定要说清楚为什么这种拆分是完备的任何合法方案至少满足其中一个条件。追问二如果房屋是一棵二叉树呢应答要点是后序遍历这棵树每个节点返回两个状态偷它和不偷它各自的收益。偷它时左右子树只能取不偷的收益不偷它时左右子树各取内部最大值。这就是树形 DP 的入门版本。追问三空间还能再优化吗到这里要稳住不是回答还可以用滚动数组——这已经做完了。正确的应答是在数组输入的设定下时间 O(n) 和空间 O(1) 已经是最优的因为必须读完整输入而递推只依赖有限前缀。能平静地说出已经达到下限比强行想出一个更花的做法更能体现水平。6.3 刷题建议与个人心得我的建议是不要孤立地刷 198 题而是把 198、213、337、2560 放在同一天按顺序刷完。每做完一道都在笔记本上写一句这道比上一道多了什么四道题刷下来你会对 DP 的状态设计、边界拆分、复杂度优化形成一套完整的直觉。我自己当初刷这题时AC 了就觉得结束了直到被面试官问dp[i] 为什么是 max(dp[i-1], dp[i-2] nums[i])回答得磕磕绊绊才意识到看懂题解和真正掌握之间隔着一整条推导链。后来带人刷题我的要求就三条能解释递推式含义能徒手写出记忆化和递推两个版本能说清每个边界分支为什么存在。做到这三点这道题才算真正属于你——而它给你的回报是后面一整个系列的 DP 题都不再陌生。