企业官网建设流程全解析

打家劫舍I和II，算是动态规划里最出圈的两道题了。说是“打家劫舍”，本质上是一个很典型的相邻选择约束问题：一排房子，每间有数额不同的现金，不能同时偷相邻两家，问最多能偷多少。第一版是直线街道，第二版把街道首尾相连围成一个环。在这两道题上，几乎可以一次看透动态规划中状态定义、递推方程、边界处理、空间压缩、环形结构拆解这一整条技术链路。我自己面试别人时也发现，能把这两题不靠背、纯靠推导写对的人，动态规划的底子一般不会差。

这篇文章会从状态定义讲起，把打家劫舍I的递推式一步步拆开，再讲II的环形怎么破，然后给出可直接复现的代码、边界用例和常见错误排查思路。最后再把同一套思路延伸到打家劫舍III以及面试里其他“相邻互斥”问题。无论你是刚开始刷动态规划、面试前突击，还是想弄明白“为什么这题这么写”，这篇文章应该能给你省下不少折腾时间。

1. 先搞清楚考点：这两道题到底在考什么

1.1 同样一套递推，换了个数据形态

先上结论：打家劫舍I和II，核心状态转移是完全一样的，区别只在于数据形态。

打家劫舍I给的是一个数组 nums，表示每间房屋的金额。要求是不能偷相邻两间，求最大能偷到的总金额。这是一个标准的线性动态规划。

打家劫舍II直接在I的基础上把街道首尾相接，变成一个环。也就是说，第一间房和最后一间房现在也是相邻的了，不能同时偷。这个变化初看就是多了一个条件，但很多人卡住的点就在这：环形结构没有天然的“起点”，上一版I里那种从第0间一路递推的思路，在环形结构下直接失效了。

这也是出题人最喜欢设置障碍的地方。同一个核心模型，换一个外壳，就能把很多人“背过模板但没理解实质”的问题暴露出来。

1.2 为什么这类题必须用动态规划，而不是贪心

我先说一个很多初学者会问的问题：既然不能偷相邻的，那是不是每次挑金额最大的偷就行了？这就是典型的贪心直觉。

拿一个例子试试：[2, 7, 9, 3, 1]。贪心的话，金额最大的是7，但偷7意味着相邻的2和9都不能偷，接下来只能偷3或1，总金额也就10左右。实际最优解是偷2、9、1加起来12。贪心在这里失灵了。

为什么会失灵？因为“当前这间偷不偷”会影响后面的决策，而且不是只看局部能判断的。这个问题天然满足两个条件：

• 最优子结构：前i间房子的最优解，可以由更短前缀的最优解推出来；
• 无后效性：一旦dp[i]确定，后面的决策只需要依赖这个结果，而不关心前i间到底是怎么偷出来的。

这两个条件正是动态规划的标志。所以这题一上来就应该确认一个思路：用DP，不要用贪心，也不要用递归硬搜。递归理论上能解，但指数级复杂度根本跑不动。

2. 打家劫舍I：把递推式从零推导一遍

2.1 状态什么定义最省事

先问一个问题：dp[i]到底表示什么？

常见的定义有两种。一种是表示“偷到第i间房时能获得的最大金额”，但要区分第i间房偷没偷，否则没法转移；另一种是表示“前i间房最多能偷到的金额”。我推荐用第二种，偷不偷第i间房的逻辑被合并进转移方程里，整体处理更干净。

定义：

dp[i] 表示从 nums[0...i] 这前 i+1 间房（也就是下标0到i）中能偷到的最大金额。

那么考虑第i间房时只有两种情况：

• 不偷第i间：那前i间的结果就等于前i-1间的结果，即 dp[i-1]；
• 偷第i间：那么第i-1间不能偷，所以结果是前i-2间的最优值加上 nums[i]，即 dp[i-2] + nums[i]。

两者取最大：

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

这个式子就是整个打家劫舍系列的地基。

边界条件也很直接：

• 只有1间房：dp[0] = nums[0]；
• 只有2间房：dp[1] = max(nums[0], nums[1])；
• 没有房：直接返回0。

注意：不要试图用一个统一的“边界处理”把nums为空的情况也套进去。我见过不少同学用长度判断时写成了 if (n <= 1) return nums[0]，结果nums为空时直接越界崩溃。空数组是必须单独处理的。

2.2 用一个具体数组把转移过程走一遍

光看公式容易飘，拿 LeetCode 官方示例里的 [2, 7, 9, 3, 1] 手算一遍。

最终答案是12。注意下标3这一行的 dp[3] 算出来还是11，说明前4间房的最优方案并没有偷第3间（值为3）。这就是“dp[i]只代表最优值，不代表一定要偷第i间”的直观体现。很多人刚学DP时老想从dp数组反推偷了哪些房子，这个以后再说，至少在这一题里不需要。

2.3 空间压缩：从数组到滚动变量

上面的推导用一整个dp数组没问题，数组长度也就是O(n)，面试时已经合格了。但如果想再进一步，可以观察转移方程：

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

发现没有，dp[i] 只依赖 dp[i-1] 和 dp[i-2]，跟dp[0]、dp[1]这些更早的状态没有任何关系。所以整个dp数组没必要全留着，只需要两个变量滚动更新。

代码长这样：

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

这里用0做初始值，省掉了数组为空的特殊判断。遍历时走到第一个元素，cur = max(0, 0+num) = num，天然实现了dp[0] = nums[0]。走到第二个元素时，prev2还是0，prev1是第一个值，cur = max(nums[0], 0+nums[1])，也就是dp[1] = max(nums[0], nums[1])。

一个小提醒：滚动变量更新顺序不能反。必须先更新 prev2 = prev1，再 prev1 = cur。反过来写，下一轮计算时用的 prev2 就被污染成了上一轮的prev1，结果全错。这种错特别隐蔽，数据量大时不容易一眼看出来。

空间复杂度从O(n)降到O(1)，复杂度没变化，但写出来的代码明显更漂亮。面试官看到这版，一般会认为你对DP的理解不只是背模板。

3. 打家劫舍II：环形结构怎么拆成线性

3.1 先理解首尾冲突到底改变了什么

现在街道变成环形，第一间和最后一间相邻。如果直接复用I的代码，结果是“可能同时偷了第一间和最后一间”，而这在II里不合法。

核心矛盾就一个：选了第一间，就不能选最后一间；选了最后一间，就不能选第一间。

所以经典做法是“分类讨论，把环拆成两个线性场景”：

• 不偷第一间：可选范围是 nums[1:]；
• 不偷最后一间：可选范围是 nums[:-1]。

分别用打家劫舍I的逻辑求出两个最大值，再取较大的那个。

为什么要用这两种情况的max，而不是其他组合？原因在于，最优解里第一间房只有两种状态：要么偷，要么不偷。如果偷，那答案一定包含在不偷最后一间的情况中；如果不偷，那答案一定包含在不偷第一间的情况中。这两种情况覆盖了所有合法方案，所以取max一定不会漏。

这个“通过枚举矛盾节点的状态来拆环”的思路，本质是一种非常通用的处理环形结构的手法，后面会再提到。

3.2 用具体例子过一遍拆环的过程

拿 [2, 3, 2] 这个经典例子来试，手动算一遍你就彻底清楚了。

• 情况A：不偷第一间，也就是考虑 nums[1:] = [3, 2]。只偷其中一间的话，取 max(3, 2) = 3。
• 情况B：不偷最后一间，也就是考虑 nums[:-1] = [2, 3]。同样，取 max(2, 3) = 3。
• max(3, 3) = 3。

答案就是3。如果直接套I的代码处理 [2, 3, 2]，会得到 dp = [2, 3, 3]，答案是3。这里居然一样，但别急着下结论说拆不拆无所谓。换一组数据 [2, 3, 2, 4] 试试：直接套I，答案是6（偷2和4，或者3和2都不到6）。但环形下首尾2和4不能同时偷，所以正确答案其实是5（偷3和2，或2和4不合法后退而求其次）。这就能看出差别了。

还有一个边界坑：当 n = 1 时，nums[:-1] 是空数组，nums[1:] 也是空数组，两个小区间都返回0，最终答案是0。但实际只有一间房，偷了就是那间房的金额。所以长度是1时必须单独判断，直接返回 nums[0]。

3.3 完整代码与复杂度

def rob_base(nums): prev2 = 0 prev1 = 0 for num in nums: cur = max(prev1, prev2 + num) prev2 = prev1 prev1 = cur return prev1 def rob(nums): n = len(nums) if n == 0: return 0 if n == 1: return nums[0] # 不偷第一间 vs 不偷最后一间 return max(rob_base(nums[1:]), rob_base(nums[:-1]))

时间复杂度O(n)：两个rob_base各自扫描一遍，合起来O(2n)，还是O(n)。空间复杂度O(1)：滚动变量和切片操作，这里注意一点，Python的切片 nums[1:] 和 nums[:-1] 会生成新数组，额外占O(n)空间。严格追求O(1)空间的话，可以给rob_base加索引参数，让它只遍历指定区间，不创建切片。

def rob_range(nums, start, end): prev2 = 0 prev1 = 0 for i in range(start, end): cur = max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = cur return prev1 def rob(nums): n = len(nums) if n == 0: return 0 if n == 1: return nums[0] return max(rob_range(nums, 0, n - 1), rob_range(nums, 1, n))

这个版本不创建切片，在内存敏感的场景（比如嵌入式环境或超大数组）更有优势。平时刷题写切片版本问题也不大，但有这个意识会让代码更扎实。

4. 实操中的常见错误与排查技巧

4.1 四个高频翻车点

第一个是边界没单独处理。nums为空、nums长度为1、长度为2，这三种情况建议都单独验证一遍。我见过太多人写完rob(nums)后拿空列表一跑就崩，或者拿 [5] 得到0。原因就是边界条件不全。

第二个是区间端点写错。打家劫舍II里，不偷最后一间的区间是 nums[:-1]，不偷第一间的区间是 nums[1:]，如果用索引版本，是 range(0, n-1) 和 range(1, n)。要特别注意range的右端是开区间，写range(0, n-2)就会漏掉倒数第二间房。

第三个是环形情况下，不假思索把“不偷第一间”理解成“必须偷最后一间”。区间 nums[1:] 只是把第一间排除，最后一间偷不偷完全由DP自由决策，不是强制偷。很多错误答案会写成rob_base(nums[1:]) + nums[-1]（强制偷最后一间），这明显违背题意，但又很容易在思路上绕进去。

第四个是滚动变量的更新顺序问题。前面提到过，先更新prev2还是先更新prev1有严格顺序。一个有效的自查办法：在纸上把两次循环的变量值都列出来，哪怕只列三行，也能发现更新顺序错在哪。

4.2 从运行结果反推问题来源

如果跑测试用例没过，先别急着改代码。我习惯先观察是哪类输入挂了：

• 普通小数组、无环、样例正常，但空数组和单元素挂了 → 边界问题。
• 结果比预期小 → 多半是DP递推里漏了状态，比如把 dp[i-2] + nums[i] 写成了 dp[i-1] + nums[i]。
• 结果比预期大 → 多半是环形约束没生效，比如直接拿I的代码跑环形数据。
• 所有数据都差一点、时好时坏 → 大概率是滚动变量更新顺序错了。

排查时最直接的做法是临时打印dp数组。即使你用滚动变量版，也可以先改成数组版，打印出每一步的dp值，和手算的表对照。这比盯着代码空想要快得多。

4.3 拿来即用的测试用例清单

以下用例建议全部跑一遍：

[] -> 0 [5] -> 5 [5, 2] -> 5 [1, 2, 3, 1] -> 4 [2, 7, 9, 3, 1] -> 12 [2, 3, 2] -> 3 [2, 3, 2, 4] -> 5 [1, 1, 1, 1] -> 2 [3, 2, 3] -> 4

最后一个 [3, 2, 3] 是环形，答案4：偷第一间和第三间，不能偷中间的2。这个用例能有效检测你的实现是不是没有正确处理首尾冲突。我之前用这组用例试过直接把打家劫舍I的代码拿来跑，结果是6，显然就错了。

5. 同一套思维还能延伸到哪里

5.1 打家劫舍III：从数组到二叉树

如果你还见过打家劫舍III，那题目形态直接从数组换成了二叉树。房子分布在二叉树节点上，相邻的父子节点不能同时偷。解题思路依然是DP，但状态定义需要扩展：

• 每个节点返回两个值：偷这个节点时的最大收益、不偷这个节点时的最大收益。
• 偷当前节点：左右子节点只能取“不偷”状态；
• 不偷当前节点：左右子节点各自取“偷或不偷的较大值”。

这已经不是本文要展开的内容了，但我想强调的是，从I到II到III，核心思想一脉相承——处理“选择某个点时，相邻点要受限”这一建模能力。数组上用一个dp[i]搞定，环上拆成两种情况，树上变成后序遍历返回两个状态。同一个题根，三种外壳。

5.2 “相邻互斥”问题的面试变形

面试里还有不少题和打家劫舍长得不一样，但模型非常接近。比如按摩师问题（不能连续预约）、粉刷房子问题（相邻不能同色）、股票问题（买卖次数限制）。它们都属于序列决策问题，递推的关键都在于“第i步的状态怎么由前面的几个有限状态转移而来”。

尤其是“环形数组”这种包装手法，在很多面试题里都会出现。处理环形的通用套路就是：枚举第一个元素的状态，把环拆成若干个线性问题。比如环形子数组最大和，也是先考虑首尾是否同时选中，再分类讨论。一旦你理解了打家劫舍II的破环方式，这类题目基本都能快速找到切入角度。

5.3 这道题真正带给你的能力

刷完打家劫舍I和II，其实你掌握的不只是两个解法和一个环形套路，而是DP入门的完整链条：如何定义状态、如何推导转移方程、如何设置边界、如何压缩空间、如何在数据形态变化时重组问题。

我在实际学习过程中的体会是，很多人卡在“照猫画虎”阶段，换一道题就不会做，原因是缺乏“把问题翻译成状态转移”的练习过程。打家劫舍系列的难度曲线非常平缓，I是最基础的线性模型，II加了环形的变形，III又换成树形结构。从简单到复杂，用同一个语义把动态规划的几个关键能力串起来，这也是为什么这个系列在面试题中的出现频率一直居高不下。

最后再分享一个小技巧：遇到这类序列决策题，先别急着写代码，先在纸上画一张小表，把dp[i-2]、dp[i-1]、dp[i] 之间的依赖关系标出来。画清楚之后你会发现，递推式根本不是背出来的，而是顺着“偷/不偷当前元素”的自然逻辑推出来的。这个习惯养成了，动态规划的题会越做越顺手。