打家劫舍这道题，算是LeetCode热门100题里“看似简单、实则后劲十足”的代表。我第一次刷的时候，以为把奇数位和偶数位的钱分别加起来、取个最大值就行，结果一提交就挂在[2,1,1,2]这种用例上。后来认真撸了一遍动态规划，才发现这道题背后藏了状态定义、转移方程推导、空间压缩、甚至环形和树形变体的全套套路，值得花时间彻底吃透。

这篇文章我会用最贴近实战的方式，把打家劫舍从暴力递归开始，逐步演进出记忆化搜索、一维动态规划、滚动数组优化，再延伸到打家劫舍II和III的解法。整个过程不是贴一行题解就完事，而是把“为什么这么做”讲清楚，顺便把我在调试中踩过的坑、穷举验证时的骚操作也一并交代。适合刚接触动态规划的读者系统入门，也适合准备面试的朋友做一次状态机思维梳理。

1. 项目概述：一道“入门简单、进阶无限”的动态规划题

1.1 打家劫舍的核心需求解析

先看题目本来的样子：你是一个专业盗贼，要沿街偷一排房子。每个房子里的金额已知，但如果你偷了相邻的两家，会触发报警。求在不触发报警的前提下，这一晚最多能偷多少钱。

我把这道题翻译成更直白的模型：有一个数组nums，你需要从中挑选一个子序列，要求挑选的下标之间至少间隔一位，让子序列的和最大。比如[2,7,9,3,1]，最优解是偷第1家、第3家、第5家，也就是2+9+1=12。

这个“不能相邻”的约束，正是动态规划能大展身手的地方。别看约束只有一个，它足以制造出反直觉的决策：有时候为了偷一个更大的值，必须要跳过连续好几家；有时候隔一家反而不如隔三家划算。所有所谓的“奇偶归并贪心”“局部最大优先”在遇到[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(maxsize=None) 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，表示一间房子都不考虑时收益为 0；dp[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)，代码反而更短。

复杂的推导之后，我用一个表格把这几种方法的复杂度放在一起，方便复习：

面试时如果只要求给出最优解，直接写双变量版就够了；但如果面试官追问“怎么想到的”，就需要把上面这条从递归到迭代的演进路线讲清楚。

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 = 0，prev1 = 0
• 读取2：cur = max(0, 0+2) = 2，更新prev2 = 0，prev1 = 2
• 读取7：cur = max(2, 0+7) = 7，更新prev2 = 2，prev1 = 7
• 读取9：cur = max(7, 2+9) = 11，更新prev2 = 7，prev1 = 11
• 读取3：cur = max(11, 7+3) = 11，更新prev2 = 11，prev1 = 11
• 读取1：cur = max(11, 11+1) = 12，更新prev2 = 11，prev1 = 12

最终答案是12，对应偷2 + 9 + 1三家的方案。这个推演过程基本就是我当年学习 DP 时在纸上做过的事情：手推三组样例，彻底搞懂每一步的语义，再也不会对转移方程产生“背公式”的恐惧。

再拿一个反直觉的用例[2, 1, 1, 2]跑一遍，看为什么简单的奇偶累加会错：

• 位置 0：cur = max(0, 0+2) = 2
• 位置 1：cur = max(2, 0+1) = 2
• 位置 2：cur = max(2, 2+1) = 3
• 位置 3：cur = max(3, 2+2) = 4

答案4，也就是偷第 1 家和第 4 家。如果只按奇偶下标分组，奇数位是2+1=3，偶数位是1+2=3，最大值只有 3，这个错误方案恰恰说明了 DP 的价值：它允许在跳过两个甚至更多房子之后，选择更优的组合。

3.4 边界条件与返回值处理

边界条件是这个题最容易翻车的地方，我把常见情况整理成一张表：

在处理n == 0时，滚动数组版本天然安全，因为循环体不执行，返回prev1 = 0。而一维 DP 版本里dp[1]会越界，必须先做特判。这也是我推荐写滚动数组版本的一个原因，少了两个分支，逻辑更紧凑。

4. 常见坑点与调试心得实录

4.1 相邻约束真的只是“隔一个”吗

我见过有人把这个题理解成“每隔一家偷一家”，然后直接按奇偶位置累加。这个理解漏掉了关键情况：最优解完全可以跳过两个甚至更多空的房子，中间隔了几家不是必须的。

举一个极端的例子：[1, 2, 3, 4, 5, 6]，按隔一家来算是1+3+5=9或者2+4+6=12，但最优解其实是2+4+6=12。这还没体现出“跳跃两格”的优势。再看[1, 2, 3, 4, 100]，隔一家最优是1+3+100=104，但如果只走“必须隔一”的路子，你会先考虑第 5 家，再回溯到第 3 家或第 2 家。实际上最优解是1+3+100或2+4+100的变体，DP 会通过dp[i-2]和dp[i-3]的叠加自动处理这些间隔。

4.2 从 0 开始循环还是 1 开始循环

这个问题的本质是“下标对齐”。在一维 DP 版本里，循环从2开始是因为要访问dp[i-2]，小于0就会越界。很多人把循环从1开始写，结果访问dp[-1]时在 Python 里不会报错，因为 Python 的负索引会从数组末尾取值，导致结果错得莫名其妙。

这点必须单独念三遍：Python 的负数下标是合法的，但它不会替你处理逻辑上的“前一个状态”，只会静默取到错误的数据。所以调试技巧第一条，建议在写 DP 时恢复“显式判断边界”，比如先特判n==0和n==1，不要依赖语言特性。

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_this：

• rob_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])。这种写法在n=2时没问题，但有些题解为了省事会把dp长度设置成n+1，让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 面试中如何清晰地说明解题过程

这道题在面试中出现频率不低，而且相爱相杀——它简单到几乎人人都能写出一版解法，但如果面试官追问“为什么不能贪心”“为什么不能只考虑奇偶下标”“空间能不能再省”，很多人就会突然卡壳。

我的建议是在面试中按四层递进讲：

1. 先用暴力递归讲清楚决策逻辑，强调“偷/不偷”的双分支。
2. 指出重复子问题的存在，引出记忆化搜索或 DP。
3. 写出 DP 数组和转移方程，带上一个手动演算的小例子。
4. 最后提滚动数组优化，并顺手说明为什么状态可以压缩。

这一套讲下来，比直接甩出一个滚动数组版本的代码更让人信服。我在模拟面试中见过不少候选人，代码写对了，但让他解释prev2和prev1的更新时回答得吞吞吐吐，说明他没有真正理解转移过程，只是背了题。

6. 一点实战心得

最后，我想分享一个自己刷题时的小经验：做完打家劫舍之后，最好立刻做一遍“打家劫舍II”和“打家劫舍III”，形成系列记忆。一个系列追下来，一维 DP、区间拆分、环形处理、树形 DP、状态压缩这几个高频考点全都过了。

还有一个小技巧：不要只在 LeetCode 的判题环境里跑，自己在本地写几组随机用例，对比一维 DP 和滚动数组的输出，顺便测一测[]、[1]、[1,2]这些边界。我的习惯是写一个三层循环的暴力枚举来做对拍器，专门对付这种“维度不高但很容易写歪”的 DP 题。

以后再遇到“不能相邻”“不能连续”“间隔选择”这类问题，我建议你先在纸上把所有状态写出来，再动手写转移方程。不要急着套模板，尤其是别一上来就背滚动数组，那会跳过最重要的思维训练。打家劫舍这道题最大的价值，不是让你记住答案，而是让你真正感受到动态规划“定义状态、推导转移、压缩空间”的完整节奏。