“打家劫舍”这四个字听起来像是什么危险行当但你打开某刷题平台的Hot100榜看到它安安静静排在动态规划那一栏就知道这其实是一道非常经典、非常适合入门的算法题。我第一次刷到它的时候第一反应是“这不就是隔一家偷一家吗”然后写了一行奇偶下标求和提交之后直接翻车。后来认认真真把状态定义、转移方程、空间优化从头推了一遍才发现这道题的价值被大多数人低估了——它不只是入门DP的模板题更是面试官考察“你怎么想问题”的一把好尺子。这篇文章我会从题目本身讲起拆解状态定义的来龙去脉给出可直接运行的代码再聊聊常见的坑以及环形、二叉树等变体怎么举一反三适合准备算法面试、或者刚接触动态规划想找一个干净例子的朋友。1. 题目到底在问什么先别急着写代码1.1 题目描述与核心约束标准题意其实很简洁一条街上有若干间房子每间房子里藏着一定数量的现金用一个数组nums表示。你是一个“专业小偷”强调一下这只是题目人设现在要决定偷哪些房子。核心约束只有一个不能同时偷相邻的两间房子因为会触发警报。问题输出在满足这个约束的前提下能偷到的最大金额。举个官方常见的例子输入[1, 2, 3, 1]最优方案是偷第1间1和第3间3得到4不能偷第2间2因为它和第1间、第3间都相邻。输入[2, 7, 9, 3, 1]最优方案是偷2 9 1 12而不是7 3 10。这道题给到的约束是nums的长度可能很大暴力枚举所有组合是指数级的必须想一个线性的办法。它本质上是“从数组中选出一组互不相邻的元素使总和最大”的决策问题。1.2 换个角度看这是一个选择模型很多人觉得“小偷”这个设定有点出戏但如果把场景换一下这道题就是非常通用的“互斥选择”模型你在排课表相邻时段不能同时排两门课每门课有价值怎么排收益最大你做项目预算分配同一个资源在相邻周期不能重复投入怎么分配产出最高你在打游戏同一行相邻格子有奖励但只能拿一个怎么拿总值最大一旦理解了这一点你就明白为什么它不是一道“脑筋急转弯”而是一类“选或不选”的决策问题。所谓“打家劫舍”只是把抽象模型包装得更有记忆点罢了。1.3 为什么不能按固定间隔来偷我最初踩的坑是把问题想成了“要么全偷奇数下标要么全偷偶数下标”。这个想法看起来很合理奇数位彼此不相邻偶数位也彼此不相邻那答案不就是两个和中取大的吗反例非常快就来了[2, 1, 1, 2]。奇数位和是2 1 3偶数位和是1 2 3看起来答案是3。但最优解是偷下标0的2和下标3的2得到4注意这里两个被选的房子中间隔了两间房。这说明间隔并不是固定一格的限制条件仅仅是“相邻不能同时选”。你可能跳一间不偷也可能连续跳两间不偷怎么跳完全取决于金额分布。这就说明你需要一个能够记忆“到当前位置为止的最优结果”的方式而不是简单套公式。动态规划就是干这个的。2. 从错误直觉到动态规划的三步演进2.1 第一反应贪心也救不了既然固定间隔不行那能不能贪心一点每次挑当前能选的最大的房子偷偷完之后删除相邻房子再继续挑看起来挺有道理但反例同样很快。考虑[3, 2, 2, 3]。如果先偷下标0的3那么下标1不能偷剩下可选的只有下标3的3下标2和0不相邻但和3相邻下标2可以和0一起吗下标2与下标3相邻不能同时选但下标2与下标0不相邻可以一起然而下标1和2相邻下标1不能偷了所以如果偷了下标0你还可以在下标2和3之间选。如果选3总收益6但其实最优是偷下标0的3和下标3的3也是6。行换一个例子。[4, 1, 1, 4]更经典贪心先偷4下标0或3不管偷哪边的4后面能选的都受限最优其实也是8。再换一个[5, 3, 4, 5]如果你先挑最大的5下标0剩下可选只有4总和9但最优是3 5 8吗不对更优是54下标0和下标2不相邻可以偷5下标04下标29或者3下标15下标38最大9。贪心碰巧也是9。真正能让贪心失败的例子是[2, 6, 3, 6, 2]先挑最大的6下标1则相邻的下标0、下标2不能选剩下可选4总和10另一个同样大的6下标3选它的话相邻下标2、4不能选剩下可选0总和8。不管哪个6贪心都不会比“26210”更差但本例最优其实是12偷下标1的6和下标3的6贪心第一步无论如何会选一个6然后它发现自己既不能同时拿两个6最优变10。那备选路径26210与最优12差2。这个例子说明局部最优的组合不一定是全局最优因为选择会互相影响。你要的是“全局状态下取最大”这正好是DP能处理的场景。2.2 为什么动态规划是天然解动态规划的核心思想是把大问题拆成有重叠的小问题用小问题的答案推出大问题的答案并记住中间结果避免重复计算。对这道题来说大问题是“前n间房能偷到的最大金额”小问题是“前k间房能偷到的最大金额”。你会发现第n间房的选择只影响相邻的第n-1间房所以前n间的结果大概率可以由前n-1间、前n-2间的结果推导出来。这也是为什么刷题平台把它放在DP入门的位置它没有复杂的图论背景、没有单调栈、没有线段树状态定义极其直白非常适合用来建立“先定义dp再推转移再定初始值”的思维框架。2.3 站在最后一间房思考如果你已经走到了第 i 间房门口你面前只有两个选择偷或者不偷。如果偷第 i 间那么第 i-1 间一定不能偷但第 i-2 间及之前不受影响你可以放心拿到前 i-2 间的最优结果再加上nums[i]。如果不偷第 i 间那第 i-1 间可以偷结果就是前 i-1 间的最优结果。两个选择谁大取谁。这一句话其实已经把状态转移方程写出来了。下一步要做的只是把“前 i 间的最优结果”这个语义落到一个数组里。3. 状态定义与转移方程推导3.1 dp 数组到底表示什么最常见的定义是dp[i] 表示从下标0到下标i这 i1 间房子中能偷到的最大金额初始值dp[0] nums[0]只有一间房时别无选择。dp[1] max(nums[0], nums[1])两间房相邻最多只能偷其中金额较大的那一间。转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])注意dp[i-1]对应“不偷第 i 间”dp[i-2] nums[i]对应“偷第 i 间”。dp[i-1]里可能已经偷了第 i-1 间也可能没偷无论哪种都不影响你现在偷第 i 间因为你干脆放弃了第 i 间。有人会好奇为什么不写成dp[i] max(dp[i-1], dp[i-2] nums[i], dp[i-3] nums[i])因为如果你偷第 i 间第 i-1 间不偷但第 i-2 间可以偷也可以不偷——dp[i-2]已经包含了第 i-2 间偷或不偷的最优结果不需要再多考虑“跳两间以上”的情况。跳两间以上偷第 i 间时中间多空出来的房间只会让你少拿钱不可能比“紧挨着空一间”更优。这个直觉很重要理解了它你就不会在转移方程里画蛇添足。3.2 另一种等价定义dp[i] 表示前 i 间房我见过不少同学用dp[i]表示前 i 间房不包含第 i 间i 从0开始的最大金额这种写法在边界上稍有不同dp[0] 0 # 0间房偷不到钱 dp[1] nums[0] # 1间房只能偷它 dp[i] max(dp[i-1], dp[i-2] nums[i-1])这里nums[i-1]是第 i-1 间房下标i-1对应前i间中最后一间。两种写法本质等价只是下标偏移一位。我自己更喜欢第一种因为写起来和题意更接近但第二种在避免数组越界时显得更优雅。面试中你只要把一种讲透就够了但心里要清楚另一种的存在因为面试官可能会追问。3.3 初始化与边界保护如果直接用dp[1] max(nums[0], nums[1])那么当nums长度为1时nums[1]会越界。所以处理流程要分情况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]判断空数组返回0这件事很多人会忽略。虽然题目通常保证至少有一间房但面试官很喜欢从边界条件观察你写代码的严谨度。空数组时小偷没得偷返回0是符合直觉的。4. 代码实现与滚动优化4.1 第一版实现一维数组O(n)空间上面这个 python 版本就是最基础的一维DP。它的时间复杂度是 O(n)空间复杂度是 O(n)。n 是房子数量。对绝大多数题目限制来说这已经能通过了。但既然这是一道经典题面试官通常会接着问一句“能不能把空间也优化一下”优化依据来自转移方程dp[i]只依赖dp[i-1]和dp[i-2]。也就是说算完当前值之后更早的dp[i-3]、dp[i-4]再也没有用武之地。那我干嘛还要开一个长度为 n 的数组呢用两个变量滚动前进就行。4.2 滚动变量版本O(1)空间def rob(nums): 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 0, prev1 0代表还没有任何房子时前“第-1间”和“第0间”之前的结果都是0。每来一间房xcur max(prev1, prev2 x)就是在“不偷这间”和“偷这间”之间取最大值。然后更新旧的prev1变成下一轮的下下层旧的cur成为下一轮的prev1。所以这个写法能直接处理空数组返回0和单元素数组cur取到x边界条件天然被吸收掉了非常优雅。面试时我会先写一维数组版再写这个滚动版展示你对空间复杂度的理解是主动的不是背结论。4.3 不同语言的实现差异用 C 或 Java 写时思路完全一样但要注意语言特性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]; }C 的话注意std::max的头文件以及数组下标的 int 溢出问题——本题金额范围不大一般不需要担心但养成用long long处理大数的习惯不亏。Python 则没有 int 溢出的困扰写起来最顺手。4.4 测试用例自查清单我每次写完代码都会跑一组自己备的用例确保没有边界问题输入期望输出说明[]0空数组[5]5单元素[1, 2]2两间房只能取较大的[2, 1, 1, 2]4跳两间的场景[2, 7, 9, 3, 1]12官方经典用例[0, 0, 0, 0]0全零偷不偷都一样[1, 2, 3, 1]4常规用例如果你用滚动变量版本[]和[5]的结果都是天然正确的。这也侧面说明那个写法在处理边界上的优势。5. 常见错误与排查经验5.1 我在刷题和面试中见过的高频错误这道题看起来短错法却五花八门。我把常见的错误整理成了一个速查表错误表现根本原因解决方式返回max(dp)而不是dp[n-1]没搞懂 dp 定义以为要取所有位置最大值dp 单调不降只需返回最后一项数组越界nums[1]报错没有处理n 1的边界先判断 n 的长度再做初始化转移方程写成dp[i] dp[i-2] nums[i]忘掉“可以不偷当前这间”的可能把不偷的情况dp[i-1]放进 max贪心或固定间隔求奇偶下标和没有意识到最优方案可能跳过多间用反例[2,1,1,2]自测写了递归没有记忆化超时没有复用子问题结果先加 memo 数组或直接转成递推滚动更新时顺序写反更新前一变量覆盖了还没用到的值先算 cur再依次移动 prev 指针其中“返回max(dp)”那条很有意思。因为 dp 数组在这个转移方程下是单调递增的老老实实返回dp[n-1]即可。如果你换成另一类“必须偷第 i 间”的状态定义才可能需要取最大值。所以写代码前把状态定义说清楚能避免一堆低级错误。5.2 从暴力递归到记忆化搜索的演进路径很多同学一上来就写 dp 数组遇到复杂题就懵。我自己的习惯是先想一个纯粹的暴力递归再找重叠子问题然后自然过渡到动态规划。以这道题为例暴力递归可以这么写def rob(nums): def dfs(i): if i 0: return 0 return max(dfs(i - 1), dfs(i - 2) nums[i]) return dfs(len(nums) - 1)这个递归逻辑是对的但时间复杂度是指数级的因为dfs(i)被反复计算。加一个memo字典缓存结果就变成了“自顶向下的记忆化搜索”def rob(nums): memo {} def dfs(i): if i 0: return 0 if i in memo: return memo[i] memo[i] max(dfs(i - 1), dfs(i - 2) nums[i]) return memo[i] return dfs(len(nums) - 1)面试时先讲递归思路再指出重复计算最后写出自底向上的 dp 循环整个逻辑链极其完整。这比上来就默写转移方程要高明得多也更能扛住追问。5.3 如何自查一个DP写法是否正确我有个简单粗暴的自查方法用样例数据手动走一遍。别嫌慢重点观察 dp 值的变化是否符合直觉。比如[2, 1, 1, 2]dp[0] 2dp[1] max(2, 1) 2dp[2] max(2, 2 1) 3dp[3] max(3, 2 2) 4每一步你都能解释清楚dp[2]意思是前三间房最多能偷3偷下标0的2和下标2的1dp[3]是四间房最多能偷4偷下标0和下标3。如果某个 dp 值出现了“越算越小”多半是你状态定义和转移方程不匹配这时候宁可停下来重新推导也不要继续往下写。6. 扩展与举一反三从线性到环形再到树形6.1 打家劫舍II环形街区怎么处理如果题目加一个条件这些房子围成了一个环第一间和最后一间也算相邻那问题就变成了“环形打家劫舍”。处理办法非常经典把环切成两个线性问题。不偷第一间只考虑nums[1:]这样最后一间和第一间没有相邻冲突。不偷最后一间只考虑nums[:-1]同样化解环的约束。答案取两者最大值。为什么这样是对的呢因为环的约束本质上只在“第一间和最后一间”之间制造了互斥只要保证二者不同时选剩下的房子就退化成一条直线。而“二者不同时选”可以被拆成“不选第一间”和“不选最后一间”两种情况覆盖。需要注意如果只有一间房nums[1:]是空数组所以要单独返回nums[0]。def rob_linear(nums): prev2 0 prev1 0 for x in nums: cur max(prev1, prev2 x) prev2 prev1 prev1 cur return prev1 def rob_circle(nums): n len(nums) if n 1: return nums[0] return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))这个扩展几乎把原题的思路复用了一遍非常适合作为面试的第二个问题。6.2 打家劫舍III从数组到二叉树再扩展一步房子排成一棵二叉树相邻节点父子关系不能同时偷。这时候一维 DP 就不够用了得用“树形DP”。思路仍然是每个节点选或不选只不过要把左右子树的结果汇总上来def rob(root): def dfs(node): if not node: return (0, 0) # (不偷当前节点的最大值, 偷当前节点的最大值) left_no, left_yes dfs(node.left) right_no, right_yes dfs(node.right) cur_no max(left_no, left_yes) max(right_no, right_yes) cur_yes node.val left_no right_no return (cur_no, cur_yes) return max(dfs(root))这里函数返回两个值no表示“当前节点不偷时子树能获得的最大金额”yes表示“当前节点偷时子树能获得的最大金额”。当前节点偷子节点只能不偷当前节点不偷子节点偷不偷随意取大的。这种思路一脉相承只是载体从数组换成了树。如果你能把线性版讲透写树形版时会顺畅很多。6.3 再往远处看这类DP题的长相打家劫舍的转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])和很多经典题有血缘关系爬楼梯dp[i] dp[i-1] dp[i-2]区别在于没有“选或不选”的权衡所以用加法。最大子序和dp[i] max(nums[i], dp[i-1] nums[i])核心是“要不要把当前元素接到前面子序列上”。0/1背包每个物品取或不取影响后续容量是一维/二维决策问题的另一种形式。股票买卖系列每天持有或卖出的状态机同样围绕“选或不选”展开。所以刷这道题真正值钱的是那个“站在当前位置列出所有可能动作用最优子结构合并结果”的思考方式。把这个想熟了热点里一大半DP题你都能找到熟悉的影子。6.4 我在实际做题时的习惯分享最后分享一个我自己的做法遇到这种经典题我会强制自己用至少两种不同的状态定义写一遍再把空间优化到最优。比如这道题先写“dp[i]表示到下标i为止的最大值”再写“dp[i]表示前i间的最大值”最后写滚动变量版本。三遍写下来你不光记住了结论还把结论之间的一致性也搞明白了。等面试被问到变体比如“变成环”或者“房子价值有负数”你也能基于对模型的理解快速调整而不是靠背题硬套。这道题属于那种“看起来短、讲起来深”的类型值得你多花点时间把它玩透。