打家劫舍这道题算是LeetCode热门100题里“看似简单、实则后劲十足”的代表。我第一次刷的时候以为把奇数位和偶数位的钱分别加起来、取个最大值就行结果一提交就挂在[2,1,1,2]这种用例上。后来认真撸了一遍动态规划才发现这道题背后藏了状态定义、转移方程推导、空间压缩、甚至环形和树形变体的全套套路值得花时间彻底吃透。这篇文章我会用最贴近实战的方式把打家劫舍从暴力递归开始逐步演进出记忆化搜索、一维动态规划、滚动数组优化再延伸到打家劫舍II和III的解法。整个过程不是贴一行题解就完事而是把“为什么这么做”讲清楚顺便把我在调试中踩过的坑、穷举验证时的骚操作也一并交代。适合刚接触动态规划的读者系统入门也适合准备面试的朋友做一次状态机思维梳理。1. 项目概述一道“入门简单、进阶无限”的动态规划题1.1 打家劫舍的核心需求解析先看题目本来的样子你是一个专业盗贼要沿街偷一排房子。每个房子里的金额已知但如果你偷了相邻的两家会触发报警。求在不触发报警的前提下这一晚最多能偷多少钱。我把这道题翻译成更直白的模型有一个数组nums你需要从中挑选一个子序列要求挑选的下标之间至少间隔一位让子序列的和最大。比如[2,7,9,3,1]最优解是偷第1家、第3家、第5家也就是29112。这个“不能相邻”的约束正是动态规划能大展身手的地方。别看约束只有一个它足以制造出反直觉的决策有时候为了偷一个更大的值必须要跳过连续好几家有时候隔一家反而不如隔三家划算。所有所谓的“奇偶归并贪心”“局部最大优先”在遇到[2,1,1,2]时都会破功因为这个用例的最优解其实是偷第1家和第4家共4元而非偷第1家和第3家3元或第2家和第4家3元。1.2 为什么它被选入LeetCode热门100题打家劫舍能进热门100题靠的是它的承上启下能力。它在剑指Offer里出现过在各大厂动态规划入门题单里也常年霸榜。原因有三点。第一它把动态规划最核心的思考路径完整走了一遍先定义状态再写转移方程最后处理边界。这套流程和背包问题、最长递增子序列、股票买卖问题完全一脉相承学会了打家劫舍等于先拿到了动态规划的通用钥匙。第二它延伸出的变体梯度特别清晰。普通版是一维数组打家劫舍II把数组首尾相连变成环形结构考察你能否拆解环打家劫舍III把数组换成二叉树变成树形DP考察你能否用递归返回值传状态。一道题追下来动态规划的基本盘就稳了。第三它的代码量虽然很少但空间优化空间很大。从递归到记忆化再到滚动数组每一层优化都有明确收益非常适合用来演示“怎么从能跑变成跑得优雅”。2. 技术思路拆解从暴力递归到状态压缩2.1 核心决策盗贼到底在决定什么我习惯在写代码前先不碰代码只描述决策过程。假设你走到了第i家你面前只有两条路偷或者不偷。如果偷第i家那第i-1家绝对不能再偷你拿到的是当前这家的钱再加上前i-2家能获得的最大金额。 如果不偷第i家那第i-1家可以自由决策你拿到的就是前i-1家能获得的最大金额。这两句话就是整道题的灵魂。动态规划里所有的状态表格、状态转移方程、递归分支都是这两句话的某种表达方式。2.2 从暴力递归到重复子问题基于这个决策过程最朴素的写法是暴力递归。定义一个函数solve(i)表示只考虑前i个房子时能偷到的最大值那么核心逻辑就是def solve(i): if i 0: return 0 return max(solve(i - 1), solve(i - 2) nums[i])这里有个值得注意的细节solve(i-1)对应“不偷第 i 家”solve(i-2) nums[i]对应“偷第 i 家”。递归出口是i 0时返回 0避免负数下标越界。暴力递归的问题很明显重复计算太多。比如solve(4)会调用solve(3)和solve(2)而solve(3)又会调用solve(2)和solve(1)solve(2)被重复计算了多次整个调用树是指数膨胀的。为了让读者直观感受这个膨胀速度我给一个很直观的类比可以想象你在一栋楼里一层层往上爬每层都要反复确认上一层的计算结果结果就是明明算过一次的数字却要反复回到过去重新计算。在nums长度为 30 的时候暴力递归就已经明显卡顿了长度到 40 以上指数爆炸基本就不可接受了。2.3 记忆化搜索把算过的结果存下来发现子问题重复后最顺理成章的优化是加备忘录。在 Python 里可以用字典也可以用functools.lru_cache把solve(i)的结果缓存下来from functools import lru_cache class Solution: def rob(self, nums: list[int]) - int: lru_cache(maxsizeNone) def solve(i: int) - int: if i 0: return 0 return max(solve(i - 1), solve(i - 2) nums[i]) return solve(len(nums) - 1)这一版的复杂度从指数级降到了 O(n)因为每个i最多只计算一次。不过递归调用本身有函数栈开销而且 Python 的递归深度默认只有 1000如果题目把数组长度拉满到 10000直接用递归就要小心栈溢出。2.4 正式切换到自底向上动态规划记忆化搜索虽好但动态规划面试里更常写的是自底向上迭代。既然solve(i)只依赖solve(i-1)和solve(i-2)我干脆开一个dp数组从前往后推。这里开始出现第一个容易搞混的细节dp[i]到底表示“前 i 个房子”还是“第 i 家为止”的最大金额两种定义都能做对但转移表达式不同。我习惯用dp[i]表示从前i个房子中能偷到的最大金额也就是下标从0到i-1这些房子。那么初始条件就是dp[0] 0表示一间房子都不考虑时收益为 0dp[1] nums[0]表示只考虑第一间房子时只能偷它。转移方程为dp[i] max(dp[i-1], dp[i-2] nums[i-1])其中dp[i-1]是“不偷第 i 间房子”的最好结果dp[i-2] nums[i-1]是“偷第 i 间房子”的最好结果。注意nums[i-1]这个下标偏移是因为dp和nums的索引体系差了 1。2.5 空间压缩滚动数组和双变量法进一步观察转移方程每一次迭代只用到dp[i-1]和dp[i-2]再往前的数值彻底没用了。所以完全不需要维护整个长度为 n 的数组只需要滚动两个变量。具体的做法是用prev2存dp[i-2]用prev1存dp[i-1]每次算完cur之后把prev1改成cur把prev2改成原来的prev1。这样空间复杂度从 O(n) 降到 O(1)代码反而更短。复杂的推导之后我用一个表格把这几种方法的复杂度放在一起方便复习方法时间复杂度空间复杂度核心思路暴力递归O(2^n)O(n) 递归栈每个位置都做“偷/不偷”双分支记忆化搜索O(n)O(n) 缓存用字典缓存已计算状态一维 DPO(n)O(n) dp 数组自底向上填表滚动数组/双变量O(n)O(1)只保留前两个状态面试时如果只要求给出最优解直接写双变量版就够了但如果面试官追问“怎么想到的”就需要把上面这条从递归到迭代的演进路线讲清楚。3. 实操环节代码实现与关键细节验证3.1 标准的一维DP模板代码先把最稳的一维 DP 写法放出来适合新手阅读也适合先保证逻辑正确再谈优化。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[n - 1]这一段有几个关键点值得说明。第一dp[i]在这里表示“到第 i 家为止能偷到的最大金额”所以初始化dp[0] nums[0]、dp[1] max(nums[0], nums[1])和前面dp[i]表示“前 i 个房子”的版本有细微差异。两种下标体系都能跑但混着用会写出让人抓狂的越界问题。第二dp[1] max(nums[0], nums[1])正好对应一个特殊场景只有两家房子时你只能选金额更大的那一家不能两家一起偷。第三循环从2开始所以需要在前面加上对n 0和n 1的边界判断否则nums[1]会越界。3.2 滚动数组优化的完整代码再给出面试中最推荐的滚动数组版本def rob(nums: list[int]) - int: prev2 0 prev1 0 for num in nums: cur max(prev1, prev2 num) prev2 prev1 prev1 cur return prev1这个版本的精妙之处在于prev2 num对应“偷当前家”而prev1对应“不偷当前家”。循环结束后prev1就是全局最大值。我第一次看到这种写法时有点不习惯总觉得变量名太抽象。所以我自己的使用技巧是在注释里把prev2写成rob_prev2把prev1写成rob_prev1这样在下一次阅读代码时不用重新推断。3.3 用实际用例验证状态转移光看代码结构新手容易产生“我知道公式但我不知道它为什么要这样滚”的感觉。手动跑一个小数组是最有效的解决办法。我以nums [2, 7, 9, 3, 1]为例用滚动数组版本逐步推演初始状态prev2 0prev1 0读取2cur max(0, 02) 2更新prev2 0prev1 2读取7cur max(2, 07) 7更新prev2 2prev1 7读取9cur max(7, 29) 11更新prev2 7prev1 11读取3cur max(11, 73) 11更新prev2 11prev1 11读取1cur max(11, 111) 12更新prev2 11prev1 12最终答案是12对应偷2 9 1三家的方案。这个推演过程基本就是我当年学习 DP 时在纸上做过的事情手推三组样例彻底搞懂每一步的语义再也不会对转移方程产生“背公式”的恐惧。再拿一个反直觉的用例[2, 1, 1, 2]跑一遍看为什么简单的奇偶累加会错位置 0cur max(0, 02) 2位置 1cur max(2, 01) 2位置 2cur max(2, 21) 3位置 3cur max(3, 22) 4答案4也就是偷第 1 家和第 4 家。如果只按奇偶下标分组奇数位是213偶数位是123最大值只有 3这个错误方案恰恰说明了 DP 的价值它允许在跳过两个甚至更多房子之后选择更优的组合。3.4 边界条件与返回值处理边界条件是这个题最容易翻车的地方我把常见情况整理成一张表输入数组期望输出说明[]0没有房子可偷[5]5只有一家直接偷[3, 1]3两家选金额更大的那家[1, 3, 1]3最优解是偷中间那家[2, 1, 1, 2]4最优解是偷首尾两家中间两家不偷在处理n 0时滚动数组版本天然安全因为循环体不执行返回prev1 0。而一维 DP 版本里dp[1]会越界必须先做特判。这也是我推荐写滚动数组版本的一个原因少了两个分支逻辑更紧凑。4. 常见坑点与调试心得实录4.1 相邻约束真的只是“隔一个”吗我见过有人把这个题理解成“每隔一家偷一家”然后直接按奇偶位置累加。这个理解漏掉了关键情况最优解完全可以跳过两个甚至更多空的房子中间隔了几家不是必须的。举一个极端的例子[1, 2, 3, 4, 5, 6]按隔一家来算是1359或者24612但最优解其实是24612。这还没体现出“跳跃两格”的优势。再看[1, 2, 3, 4, 100]隔一家最优是13100104但如果只走“必须隔一”的路子你会先考虑第 5 家再回溯到第 3 家或第 2 家。实际上最优解是13100或24100的变体DP 会通过dp[i-2]和dp[i-3]的叠加自动处理这些间隔。4.2 从 0 开始循环还是 1 开始循环这个问题的本质是“下标对齐”。在一维 DP 版本里循环从2开始是因为要访问dp[i-2]小于0就会越界。很多人把循环从1开始写结果访问dp[-1]时在 Python 里不会报错因为 Python 的负索引会从数组末尾取值导致结果错得莫名其妙。这点必须单独念三遍Python 的负数下标是合法的但它不会替你处理逻辑上的“前一个状态”只会静默取到错误的数据。所以调试技巧第一条建议在写 DP 时恢复“显式判断边界”比如先特判n0和n1不要依赖语言特性。4.3 打家劫舍II环形数组的拆解思路打家劫舍II把数组首尾相接形成环。核心变化是第 1 家和最后一家现在成了邻居不能同时偷。处理思路很直接分成两种情况分别求最大。情况一不偷第 1 家那么可以在从第 2 家到最后一家的范围内正常求解。 情况二不偷最后一家那么可以在从第 1 家到倒数第 2 家的范围内正常求解。两种情况的答案取最大值。代码可以复用同一个“线性打家劫舍”函数有如下模板def rob_linear(nums: list[int]) - int: prev2 0 prev1 0 for num in nums: cur max(prev1, prev2 num) prev2 prev1 prev1 cur return prev1 def robII(nums: list[int]) - int: if len(nums) 1: return nums[0] return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))这里有个非常隐蔽的细节我第一次写的时候直接踩了当数组长度为 2 时nums[:-1]和nums[1:]分别只包含一个元素跑出来的答案没问题。但当数组长度为 1 时两个切分出来的都可能是空数组rob_linear([])返回 0可正确答案是唯一的那个数所以必须单独特判len(nums) 1。4.4 打家劫舍III树形DP的状态返回到了打家劫舍III房子变成一棵二叉树不能同时偷父子节点。此时“一维数组”的思路失效递归的返回值要携带两个信息当前节点被偷时的最大值以及当前节点不被偷时的最大值。设计一个递归函数dfs(node)返回两个值rob_this和not_rob_thisrob_this node.val left_not_rob right_not_rob表示偷当前节点时左右子节点都不能偷。not_rob_this max(left_rob, left_not_rob) max(right_rob, right_not_rob)表示不偷当前节点时左右子节点各自取最优。最终答案是max(dfs(root))。这个结构很有意思它把“状态”从单个数组下标升级成了“每个节点两个状态”等于是打家劫舍系列从一维 DP 走向了树形 DP 的自然过渡。4.5 一个很多人忽略的初始化问题有些读者写的dp [0] * n然后在循环里把dp[1] max(nums[0], nums[1])。这种写法在n2时没问题但有些题解为了省事会把dp长度设置成n1让dp[i]表示“前 i 个房子”的收益。此时循环从1到n结论是dp[n]。两套定义得到的返回下标不一样一个是dp[n-1]一个是dp[n]差之毫厘谬以千里。我的建议是刷题时固定一套习惯不要每次重新定下标。我自己固定用“前 i 个房子”体系返回dp[n]因为这样边界更少空数组也自然处理。5. 从打家劫舍延伸出来的通用模型5.1 状态机视角两个状态的自动机如果把“偷/不偷”看作两个状态打家劫舍就是一个简单状态机状态 A不偷当前家可以从“上一家偷”或“上一家不偷”转移过来。状态 B偷当前家只能从“上一家不偷”转移过来并且要加上当前金额。用两个变量维护这两个状态代码是这样rob 0 not_rob 0 for num in nums: new_rob not_rob num new_not_rob max(rob, not_rob) rob, not_rob new_rob, new_not_rob这个视角一旦建立起来再去看股票买卖、打家劫舍III、甚至一些序列预测问题都会顺畅很多。“持有/不持有”“选/不选”、这类二状态模型几乎遍布所有常见 DP 题。5.2 怎么把打家劫舍模板迁移到其他题迁移的思路是三步走先找“状态”再找“转移”最后压缩“空间”。拿“打家劫舍II”来说它的状态还是“前 i 个房子的最大收益”但环形约束改变了转移的适用范围所以要重新拆分求解区间。拿“打家劫舍III”来说状态从一维变成了“每个节点的两个取值”思路仍然是递推只是载体变成了树。我自己做算法题最大的体会是模板不用死记但要理解每一道题为什么这样定义状态。比如背包问题里的“容量”是第二个维度股票问题里有“是否持有”的状态维度打家劫舍系列则是“不相邻选择”的后效性消除。只要把状态定义清楚剩下的转移方程基本就是把语言描述直接翻译成代码。5.3 面试中如何清晰地说明解题过程这道题在面试中出现频率不低而且相爱相杀——它简单到几乎人人都能写出一版解法但如果面试官追问“为什么不能贪心”“为什么不能只考虑奇偶下标”“空间能不能再省”很多人就会突然卡壳。我的建议是在面试中按四层递进讲先用暴力递归讲清楚决策逻辑强调“偷/不偷”的双分支。指出重复子问题的存在引出记忆化搜索或 DP。写出 DP 数组和转移方程带上一个手动演算的小例子。最后提滚动数组优化并顺手说明为什么状态可以压缩。这一套讲下来比直接甩出一个滚动数组版本的代码更让人信服。我在模拟面试中见过不少候选人代码写对了但让他解释prev2和prev1的更新时回答得吞吞吐吐说明他没有真正理解转移过程只是背了题。6. 一点实战心得最后我想分享一个自己刷题时的小经验做完打家劫舍之后最好立刻做一遍“打家劫舍II”和“打家劫舍III”形成系列记忆。一个系列追下来一维 DP、区间拆分、环形处理、树形 DP、状态压缩这几个高频考点全都过了。还有一个小技巧不要只在 LeetCode 的判题环境里跑自己在本地写几组随机用例对比一维 DP 和滚动数组的输出顺便测一测[]、[1]、[1,2]这些边界。我的习惯是写一个三层循环的暴力枚举来做对拍器专门对付这种“维度不高但很容易写歪”的 DP 题。以后再遇到“不能相邻”“不能连续”“间隔选择”这类问题我建议你先在纸上把所有状态写出来再动手写转移方程。不要急着套模板尤其是别一上来就背滚动数组那会跳过最重要的思维训练。打家劫舍这道题最大的价值不是让你记住答案而是让你真正感受到动态规划“定义状态、推导转移、压缩空间”的完整节奏。