企业官网建设流程全解析

刷LeetCode刷到“打家劫舍”这道题的朋友，应该都体会过那种感觉：题目读起来很简单，一排房子，相邻两间不能同时进，求能偷到的最大金额。但真到了要写状态转移方程的时候，脑子容易绕进去，尤其是刚接触动态规划的同学，经常卡在边界条件和dp数组的定义上。作为LeetCode热门100题里的经典动态规划入门题，它几乎是面试高频题单里的标配，也是后续打家劫舍II、打家劫舍III的基石，周赛里偶尔还会出现它的变体。这篇文章就围绕这道题，把动态规划的思路拆开揉碎，从最朴素的递归想法一路推导到空间O(1)的滚动数组写法，再用我实际刷题踩过的坑给你提个醒。适合正在刷题准备面试的读者，也适合刚学动态规划、想搞懂“状态”到底是什么的初学者。

1. 打家劫舍到底在问什么：三个最容易被忽略的边界条件

1.1 题面约束的本质：相邻房间的互斥关系

原题描述很直接：你是一个小偷，沿街有一排房屋，每个房屋里有特定金额的现金，不能偷相邻的两间房，否则会触发报警，问最多能偷多少。LeetCode第198题，英文名叫House Robber。它和热词里常被刷到的LeetCode热门100题、题解、周赛430挂钩，说明这题的出场率确实不低。

很多人第一次看题，第一反应是“隔一家偷一家”，然后把数组分成奇数和偶数下标两个集合，分别求和取大者。这个思路是错的，我给你举反例：

nums = [2, 7, 9, 3, 1] 奇数下标（索引1、3）：7 + 3 = 10 偶数下标（索引0、2、4）：2 + 9 + 1 = 12 奇偶取大是12，但正确答案是12吗？

走一遍：偷索引0（2）和索引2（9）和索引4（1），总和12，且不相邻，没问题。但再试另一种组合：偷索引0（2）、索引2（9），跳过索引3，偷索引4（1），这其实就是奇偶方案。可如果把索引1（7）和索引3（3）加进去，就冲突了。真正的最优解是偷索引1（7）和索引3（3），加上索引4（1）不行，因为3和4相邻；所以是7 + 3 = 10，然后试试偷0（2）、2（9），不偷3，偷4（1），共12，这个更优。等一下，我重新手算一下这个例子的正确结果。

数组[2, 7, 9, 3, 1]，我们要选一个子序列，不能选相邻元素，求最大和。可选组合：

• 偷0、2、4：2 + 9 + 1 = 12
• 偷0、2：11
• 偷0、3：5
• 偷0、4：3
• 偷1、3：10
• 偷1、4：8
• 偷2、4：10
• 偷0、2、4 = 12，偷2单独 = 9，偷1 = 7，偷3 = 3，偷4 = 1
• 偷0、2不行和偷1冲突吗，不，0和2不相邻，1和3不相邻，但0和1相邻、2和3相邻。所以0、2、4合法，12是解；1、3合法，10。 所以最大确实是12，奇偶方案碰巧对了。这就是这个反例不够有力，它恰好让奇偶方法也得到12。再构造一个反例：[3, 2, 1]，奇数下标（索引1）= 2，偶数下标（索引0、2）= 3+1=4，奇偶取大4；但偷索引0和2不相邻吗？索引0和2不相邻，之间隔了索引1，所以3+1=4，也是对的。这个例子也不行。

真正能拆穿奇偶法的例子是[2, 1, 1, 2]。奇数下标（索引1、3）：1 + 2 = 3；偶数下标（索引0、2）：2 + 1 = 3，奇偶取大3；但最优解是偷索引0（2）和索引3（2），中间隔了1和2两个房间，不相邻，总和4。奇偶法在这里会漏掉最优解。这个例子说明，“固定隔一个偷一个”是错误直觉，因为最优解完全可能跳过两个或更多的房间，只在你认为收益最大的地方下注。所以这道题不能用“按下标奇偶分组”的方式解，必须考虑每个房子“偷还是不偷”的决策。

1.2 空数组和单元素数组：边界条件的魔鬼细节

LeetCode的测试用例里，nums为空、nums只有一个元素这两种情况一定会出现。很多新手在写动态规划时，初始化dp数组长度为n，然后写dp[1] = nums[1]，如果n等于1，这一行直接数组越界。这也是为什么我在实际刷题时，第一件事就是先把空数组和长度1的用例在草稿纸上过一遍。

单元素数组的最好处理方式是在初始化时直接做判断：

n = len(nums) if n == 0: return 0 if n == 1: return nums[0]

这两行看起来啰嗦，但对于后面所有递推代码的稳健性至关重要。而且LeetCode里这种输入很常见，有时候题目会给[]这种极简用例，如果你不在最前面兜住，后面写再漂亮的转移方程也会在第一行就崩。

1.3 状态定义要先于递推公式

我一直觉得，动态规划题能不能做出来，一半以上取决于状态定义是否清晰。打家劫舍这题，最常见的定义是：

dp[i]表示从第0间房子到第i间房子（包含第i间）这一段里，能偷到的最大金额。

有了这个定义，递推关系就容易表达了：对于第i间房子，你有两个选择，要么偷它，要么不偷它。如果偷它，因为它和第i-1间相邻，所以第i-1间就不能偷，此时总金额是dp[i-2] + nums[i]；如果不偷它，那第i-1间是否被偷无所谓，总金额就是dp[i-1]。取这两种选择的最大值，就是dp[i]。

这里有个细节要强调：dp[i]并不是“在必须偷第i间的前提下”的最大值，而是“考虑前i+1间房子时”的最大值。我见过不少同学把状态定义成“偷到第i间房时的最大金额”，然后递推时把dp[i]写成dp[i-2] + nums[i]，没有跟dp[i-1]做比较，这样会漏掉大量更优的不偷方案。状态定义差一个字，整个转移方程就彻底变味了。

2. 从暴力递归到动态规划：状态转移方程的推导全过程

2.1 为什么暴力搜索会指数爆炸

在动态规划被发明之前，先想一下暴力解法长什么样。对于每间房子，都有“偷”和“不偷”两个选择，而且这两个选择还会影响后面的房子。如果n是10，可能存在2的10次方种方案；n是50，方案数就是天文数字。暴力递归的做法会重复计算大量子问题，比如你在递归树的左侧计算了rob(0, 4)，右侧可能又要计算一次rob(0, 4)，这种重叠子问题是动态规划可以优化的基础。

打家劫舍这题有个特别适合人类直觉的递归写法：

def rob_rec(nums, i): if i < 0: return 0 return max(rob_rec(nums, i - 1), rob_rec(nums, i - 2) + nums[i])

这个递归的逻辑是：站在第i间房子门前，要么不进去，去考虑前i-1间；要么进去偷，但前提是第i-1间被跳过，所以回到第i-2间。边界是i小于0时返回0。这其实就是dp[i] = max(dp[i-1], dp[i-2] + nums[i])的递归形态。

很多教学材料直接给你递推公式，却不说它是怎么来的。我建议时间充裕的读者，先把这个递归函数在纸上跑一遍[2, 7, 9, 3, 1]，画一棵递归树，你会很直观地看到同一个子问题被反复计算多次。比如rob(3)被rob(4)和rob(3)的上级各自调用，整个树的节点数接近指数级。这时候再把递归树中相同节点缓存结果，就是带备忘录的递归；进一步改成从底向上填表，就是标准的动态规划。

2.2 从递归到填表：自底向上的完整手算

把递归改成迭代，最重要的转变是思考方向：递归是从第n-1间往前推，动态规划是从第0间往后推。我们要先初始化前两个状态，然后依次计算后面的所有状态。

按照dp[i]的定义，初始化应该是：

• dp[0] = nums[0]，只有一间房时，不偷白不偷，最大收益就是它本身。
• dp[1] = max(nums[0], nums[1])，有两间房时，必须在第0间和第1间里二选一，因为相邻不能同时偷。

然后从i=2开始遍历到n-1，执行状态转移：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

我拿[2, 7, 9, 3, 1]实际走一遍，你感受一下填表的过程：

最终dp[4]=12，对应正是偷第0、2、4间房，总金额12。注意i=3的时候，dp[3]是11，而不是10，说明最优策略在第三间房时选择了不偷第3间，维持了前两间的最优状态。这种“当前最优状态可能在某个位置选择跳过”的特性，恰恰是上一节里奇偶分组法会漏解的根本原因。

2.3 为什么最终答案就是dp[n-1]

这是很多初学者最后一步会犯嘀咕的地方：题目要求整条街的最大收益，为什么就是最后一个状态呢？因为dp[i]的定义是“考虑前i+1间房时的最大金额”，当i遍历到n-1时，它已经考虑了所有的房间，所以它的值就是全局最优解。

这里要区分一个概念：dp[n-1]和dp[n-2]在实际中可能相等，比如刚才例子里dp[3]=11、dp[4]=12，不相等；但如果你遇到[2, 1, 1, 2]，dp[2]=max(dp[1], dp[0]+1)=max(2,3)=3，dp[3]=max(dp[2], dp[1]+2)=max(3,4)=4。最后一间房被偷了。有时候最后一间房不被偷，dp[n-1]就等于dp[n-2]。这没关系，你只需要返回dp[n-1]，它就是全局最大，因为如果不偷最后一间能拿到更大收益，dp[n-1]会自动取到dp[n-2]的值。

我之前见过有人非要返回max(dp)，这样也能过，但没必要，而且会让代码显得不干净。在面试场景里，面试官问“返回值为什么是这个”，你能解释清楚“dp[n-1]已经是考虑完全部房屋的最优值”，这比“我直接取了数组最大值”要好得多。

3. 空间复杂度从O(n)降到O(1)：滚动数组的原理与坑

3.1 转移方程为什么只依赖前两个状态

观察dp[i] = max(dp[i-1], dp[i-2] + nums[i])，你会发现dp[i]的计算只用到dp[i-1]和dp[i-2]，再往前（dp[i-3]、dp[i-4]之类）完全没有参与。这意味着用一整个dp数组来装所有历史状态是浪费的——我们只需要记住最近的两个状态，就可以一路把答案算到底。这就是滚动数组（滑动状态）的核心思想：把动态规划数组压缩成有限个变量。

打个生活化的比方：你走台阶，每次只看得到前两级台阶上放着什么，不需要把走过的所有台阶都拍下照片放在口袋里。只需要记住“上一级的结果”和“上上一级的结果”，走到第i级时，用这两个值推导当前，然后把“上一级”降级为“上上一级”，把“当前”变成新的“上一级”，继续往前走。

3.2 两个变量加一个临时变量的经典写法

一个最常见的滚动数组实现是这样的：

def rob(nums): n = len(nums) if n == 0: return 0 if n == 1: return nums[0] prev2 = nums[0] # dp[i-2]的初始值 prev1 = max(nums[0], nums[1]) # dp[i-1]的初始值 for i in range(2, n): cur = max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = cur return prev1

这里prev2对应dp[i-2]，prev1对应dp[i-1]。循环开始时i=2，所以prev2=nums[0]即dp[0]，prev1=max(nums[0], nums[1])即dp[1]，正好是转移方程需要的前两个状态。每轮循环算出cur后，把prev1赋值给prev2，把cur赋值给prev1，这样就完成了状态滚动。

这是最稳妥的写法。你可能见过网上有人用三个变量a、b、c来做同样的滚动，还有人用Python的并行赋值一行搞定：

prev2, prev1 = nums[0], max(nums[0], nums[1]) for i in range(2, n): prev2, prev1 = prev1, max(prev1, prev2 + nums[i]) return prev1

并行赋值在Python里是“等号右边先整体求值，再统一赋值”，所以不会出现中间变量被覆盖的问题，能少写一行tmp。但我个人建议在面试手写代码时用带临时变量的版本，因为它在任何语言里都可移植，而且逻辑对面试官来说更透明。用并行赋值虽然优雅，但如果面试官用的是C++或Java，你得临时改成int temp = b; b = max(...); a = temp;，思路还得重新转一圈。

3.3 滚动数组最经典的翻车现场：更新顺序写反

我曾经在给朋友review代码时看到过这样一段：

prev2 = nums[0] prev1 = max(nums[0], nums[1]) for i in range(2, n): prev2 = prev1 prev1 = max(prev2, prev2 + nums[i]) # 这里的prev2已经被覆盖了 return prev1

看出来了吗？在计算max(prev2, prev2 + nums[i])之前，prev2已经被prev1覆盖了。于是prev2 + nums[i]变成了prev1 + nums[i]，递推变成了dp[i] = max(dp[i-1], dp[i-1] + nums[i])，相当于忽略“跳过前一个房间偷当前房间”的收益加成。这个错误极难靠肉眼察觉，因为大部分测试用例都能算出看起来差不多的结果，只有在特定数组上才会差个几块钱。我在刷题时吃过这个亏，后面养成了一个习惯：凡是滚动数组更新，都会先把旧值存进临时变量，再用临时变量参与所有计算，更新顺序严格遵循“先求值，再滚动”。

3.4 什么时候必须保留完整dp数组

滚动数组省空间，但也丢掉了“历史最优路径”。如果题目稍微改一下，要求你输出偷的是哪几间房，或者要求你解释dp在哪个位置发生了“不偷”的决策，滚动数组就无能为力了。LeetCode原题只需要返回金额，用滚动数组没问题；但如果面试官现场加问“能不能把偷的房间序号也输出”，你就要立刻切回完整dp数组方案，并反推决策：

# 完整dp数组反推路径 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]) # 从后往前反推选了哪些房间 result = [] i = n - 1 while i >= 0: if i >= 1 and dp[i] == dp[i-1]: i -= 1 else: result.append(i) i -= 2 result.reverse()

这个小扩展在面试中经常被问到，建议你提前练一下。它的逻辑也不复杂：如果dp[i]等于dp[i-1]，说明第i间没有被偷，往后退一格；否则说明偷了第i间，把i加入结果，然后跨过第i-1间，直接跳到i-2继续判断。

4. 完整AC代码与真实调试心得：这题在面试和笔试里的隐藏考点

4.1 一份可以直接用的标准实现

把前面所有要点合并成一份完整代码，我平时在LeetCode提交的就是这个版本：

from typing import List class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 0: return 0 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

这是我在LeetCode上最终定稿的样子。类型注解List[int]可有可无，但写上之后对IDE的自动补全更友好，也更容易让面试官觉得你代码习惯好。时间复杂度O(n)，只遍历了一遍数组；空间复杂度O(1)，常数个额外变量。

4.2 我每次都要跑的一组测试用例

调试动态规划题，最怕的就是“测试用例太温和，错误代码也能跑出正确答案”。所以我给自己列了一个标准清单，每次写完打家劫舍都会先拿这组用例过一遍：

特别注意[2, 1, 1, 2]这个用例。如果你写的是“把数组拆成奇偶下标算和再比较”的思路，它会直接输出3，但正确答案是4。很多人在网上发题解时，自己用的也是错的奇偶思路而不自知，原因就是他们没跑过这个反例。这种测试用例本身就是最好的学习材料，能帮你验证状态转移方程是不是真的考虑了所有决策。

4.3 初始化的两种常见写法，以及各自容易踩的坑

我在网上看过很多题解，初始化方式五花八门，但归结起来主要有两种。第一种是上面代码里的prev2 = nums[0], prev1 = max(nums[0], nums[1])，这种写法的好处是跟dp数组的初始化一一对应，逻辑直白，不容易算错i的起始位置。第二种是造一个长度为n+1的dp数组，约定dp[0] = 0表示没有房子时收益为0，dp[1] = nums[0]，然后从i=2开始递推，递推公式里的下标要整体偏移一位：

dp = [0] * (n + 1) dp[1] = nums[0] for i in range(2, n + 1): dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]) return dp[n]

这种写法在竞赛圈也常见，优点是空数组不需要单独判，dp[0]天然就是0；缺点是下标偏移容易看花眼。我自己两种都写过，结论是：只要你能保证循环体内所有的nums下标都做了减一处理，第二种写法就能work；但如果你在写转移方程时复制粘贴漏了一个-1，调试起来会非常痛苦。给新手读者的建议是选第一种，把下标和含义一一对应，不容易出错。

4.4 面试现场被追问的表现建议

打家劫舍在面试里出现时，很少有人直接扔你一道裸题。面试官常见的加问有：为什么不能用贪心？为什么奇数下标之和不是答案？你能把它改成输出路径吗？你能否把空间压缩到O(1)？

关于贪心，我见过有人说“每次都看下下家，如果下下家更大就跳过当前”，这类局部最优策略很容易举出反例。比如[2, 1, 1, 2]，站在索引0看，下下家是索引2的1，小于当前的2，于是偷0；然后到索引1，下下家是索引3的2，大于1，跳过1，到索引3直接偷2；这样得到的是2+2=4，居然对了。再换[3, 2, 1, 3]，索引0看下下家1，偷3；索引1看下下家3，大于2，跳过；索引3偷3，得到6。但正确解法是索引0和索引2：3+1=4，或者索引1和索引3：2+3=5，都不是6。等等，索引0的3和索引3的3不相邻，中间隔了2和1两个房间，应该是6！这个反例又不对。我再认真找一个贪心失效的例子：[5, 3, 4, 11, 2]，贪心看当前和下下家：索引0的5大于下下家4，偷5；索引1的3小于下下家11，跳过；索引2的4小于下下家2吗？不大于，所以偷4；索引3的11大于下下家2，偷11；索引4的2最后偷？但索引3偷了，索引4不能偷。结果5+4+11=20？不对，4和11之间隔了索引3？索引2偷了4，索引3的11可以偷，因为不相邻，结果5+4+11=20。但最优解是索引1和索引3：3+11=14，或者索引0、索引2、索引4：5+4+2=11，都没到20。贪心得到了20，比最优还高？说明贪心选的序列可能不合法——等等，检查一下：贪心第一步偷索引0，那索引1不能偷；第二步看索引1的3下下家索引3的11，11大，跳过1；第三步看索引2的4，下下家索引4的2，4大，偷2；第四步索引3被跳过？贪心看索引3是因为之前跳过了？这里贪心算法没有统一的明确定义，说不清楚。

所以在面试里讨论贪心，更稳妥的切入点是直接说明：这题本质上是一个二维决策问题，每个房子选与不选会影响相邻选项，贪心无法保证全局最优，而动态规划通过记录每个前缀的最优解，天然覆盖了所有合法方案。你不需要去构造复杂反例，只需要指出“贪心的局部最优判断无法感知全局的收益分布”，然后补一句“如果你愿意，我可以现场构造一个反例”，这一般就够了。真正的关键还是把动态规划的状态定义和转移逻辑讲清楚。

4.5 调试时最值得打印的信息

如果你在本地调试这类题，不要一上来就print整个dp数组。我调试滚动数组版本时，通常只打印每次循环的i、prev2、prev1和cur四个值。这样能快速定位是更新顺序错了还是初始值错了。经典错误之一是prev1的初始化写成nums[1]，导致当数组长度为2、且第二个元素小于第一个元素时，答案直接算错。打印初始化之后的prev2、prev1，立刻就能发现问题。

5. 打家劫舍系列怎么学：从线性到环形，再到树形

5.1 打家劫舍II：环形数组怎么拆

原题是一排房子，打家劫舍II（LeetCode 213）变成了一圈房子，第0间和第n-1间相邻。这样你首尾不能同时抢，思路就变成了“分情况讨论”：要么不抢第0间，把第1间到第n-1间当作线性数组来求；要么不抢第n-1间，把第0间到第n-2间当作线性数组来求。两种结果取最大值即可。这里有个细节：如果你把仅有一间房的情况单独处理，两个子数组就分别是nums[1:]和nums[:-1]，都能复用同一个一维打家劫舍函数。现实中环形数据结构不少见，这种“拆环为链”的思路在很多题目里都能复用，所以很值得顺便学一学。

5.2 打家劫舍III：树形DP与状态返回值的妙用

再进阶一步，打家劫舍III（LeetCode 337）把数组换成了二叉树。房子沿二叉树分布，不能同时抢直接相邻的两个节点（父子节点）。这时线性dp的数组递推不再适用，需要换成树形动态规划。常规做法是定义递归函数dfs(node)，返回两个值：rob表示抢当前节点能得到的最大金额，not_rob表示不抢当前节点能得到的最大金额。转移关系是：

• 抢当前节点时，左右孩子都不能抢，rob = node.val + left.not_rob + right.not_rob
• 不抢当前节点时，左右孩子各自取最大，not_rob = max(left.rob, left.not_rob) + max(right.rob, right.not_rob)

这个做法的核心思路跟线性版完全同源，都是“当前节点抢不抢”的决策，只不过把一维数组的上下文变成了树的后序遍历。很多人在学完198之后直接去啃337，会被递归和双返回值搞晕；但如果你先把线性版的状态定义吃透，再看树形版，本质就是同一套思维在不同数据结构上的映射。

5.3 三道题放在一起的复习路径

我比较推荐的学习节奏是把198、213、337看作一个系列，逐层递进。先确保自己能十分钟内默写出线性版滚动数组代码，再尝试把线性版抽成一个工具函数，去跑213的两个子数组，最后再碰337的树形DP。一道题单独做可能印象不深，但三道题放在一起刷，你会很明显地看到：从数组到环形数组到二叉树，变化的只是数据的排列方式，不变的永远是“选或不选，并保证不选相邻冲突”的决策框架。

有一件事我每次刷动态规划这方面的题都想强调：状态定义里的“考虑前i个”这个措辞，值得反复咀嚼。它意味着dp[i]并不强制要求第i个元素被选中，它只是一个前缀范围内的最优解容器。很多玄学错误，说到底都是把“考虑”理解成了“必须选”。想通了这一点，打家劫舍系列的一道题和后面的很多变体都会顺畅很多。你在纸上把[2, 1, 1, 2]的dp数组手算一遍，再对比滚动数组每轮变量的变化，就会发现动态规划并没有那么玄，它只是在用表格记录“每一步做选择时，前面已经算好的最优答案”罢了。