企业官网建设流程全解析

“打家劫舍”这个题目，只要是刷过LeetCode动态规划板块的朋友肯定都不陌生。它常年霸榜在DP入门题单里，被无数人当作理解状态转移的第一道关。但有意思的是，很多新手刷完198题“打家劫舍”觉得懂了，一碰到213题“打家劫舍 II”就傻眼——明明代码长得差不多，为什么多了一个“环形”条件，思路就完全接不上？

这篇文章我就把这两道题放在一起，完整拆解从线性DP到环形DP的推导过程、代码实现、状态压缩思路，以及我在实际刷题过程中踩过的坑和积累的排查经验。不管你是刚接触动态规划的新手，还是准备面试想快速过一遍经典题型的同学，这篇文章都应该能给你一些可以复用、可以直接抄作业的思路。

1. 为什么“打家劫舍”是动态规划教学的第一课

1.1 一个看起来像“贪心”但贪心解不了的题

先看题目本身的场景。假设你是一个专业小偷，打算盗窃一整条街沿街的房子，每间房内都藏有一定现金，但有一个限制：你不能偷窃相邻的两间房屋，不然会惊动安保系统。现在给你一个数组 nums，每间房内的现金数，要你计算在不触发警报的情况下，今晚能偷到的最大金额。

很多第一次接触这道题的人，第一反应是：这不就是贪心吗？我每隔一间偷一间不就行了？比如数组是 [2, 1, 1, 2]，按“跳着偷”的逻辑，可能会选择第0间和第2间，得到 2 + 1 = 3；或者选择第1间和第3间，得到 1 + 2 = 3。但正确答案其实是第0间和第3间，也就是 2 + 2 = 4。你看，贪心的局部最优在这里根本靠不住，因为你跳过去的那一间，有可能才是真正的大头。

那这题考察的是什么？它考察的是你面对一个“每一个当前选择都会影响后续所有选择”的场景时，能不能把问题拆解成规模更小的子问题，并用状态记录下来。这就是动态规划的核心思想：将一个问题拆分成相互关联的子问题，通过子问题的最优解来推导出原问题的最优解。

1.2 从约束条件到状态定义

“相邻不能一起偷”这个约束，翻译成数学语言其实非常优美。假设我们站在第 i 间房子面前，面临两个选择：

• 方案A：偷第 i 间房，那么第 i-1 间房肯定不能偷，此时最大金额 = 前 i-2 间房的最大值 + nums[i]；
• 方案B：不偷第 i 间房，那么第 i-1 间房可以偷，此时最大金额 = 前 i-1 间房的最大值。

我们要的答案，就是这两个方案里较大的那个。这个逻辑看起来简单，但它本质上构成了一张由“前 i 间房最大偷窃金额”串起来的递推链条。你不需要知道具体的偷窃路径，只需要知道每个位置上的最优值，因为它已经是一个全局最优的子结果。

这也就是为什么“打家劫舍”系列会成为经典教学案例：它没有复杂的图论模型，不需要记忆化搜索的递归技巧，纯粹靠一个数组和一行递推公式就能推导完整。理解这个问题，你就理解了DP里最基础也最重要的一层概念——状态定义和状态转移。

2. 打家劫舍 I：线性DP完整推导

2.1 状态定义与转移方程的每一步

我们先给 198 题“打家劫舍”下手。假设输入数组是 nums，长度为 n，我用 dp[i] 表示“从第 0 间房到第 i 间房能偷到的最大金额”。注意，这里 dp[i] 并不是说“一定偷第 i 间”，而是“考虑了前 i 间房这个整体范围后的最优结果”。这个区分非常关键，很多坑都是从这一步开始埋下的。

边界条件很简单：

• 当 n = 0 时，一间房都没有，金额自然是 0；
• 当 n = 1 时，只有一间房，直接偷它，金额就是 nums[0]；
• 当 n = 2 时，两间房不能同时偷，所以取 max(nums[0], nums[1])。

从 n ≥ 3 开始，递推公式就接管了：

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

逐项解释一下这个公式在说什么。dp[i-1] 代表“不偷第 i 间房，那么第 i-1 间房可偷不可偷都无所谓，反正前 i-1 间的最优结果已经是现成的”。dp[i-2] + nums[i] 代表“偷第 i 间房，那么第 i-1 间必须跳过，只能从前 i-2 间的结果上叠加 nums[i]”。两个方案取大的，就是前 i 间的最优解。

为了验证这个递推的合理性，我们拿一个例子走一遍。设 nums = [2, 7, 9, 3, 1]，这个数组是题目官方示例，大家都很熟：

• dp[0] = 2
• dp[1] = max(2, 7) = 7
• dp[2] = max(dp[1]=7, dp[0]+9=11) = 11
• dp[3] = max(dp[2]=11, dp[1]+3=10) = 11
• dp[4] = max(dp[3]=11, dp[2]+1=12) = 12

最终结果是 12，对应偷第1间（7元）和第4间（4号位置，1元），等等，这里要小心，结果是 7 + 9 = 16？不对，我重新算一下。dp[4] = max(11, dp[2]+nums[4]=11+1=12) = 12。但实际最大化是 dp[3]=11，对应选择第2间（9）和第0间（2），合计 11；或者第1间（7）+第3间（3）=10；或者第1间（7）+第4间（1）=8。看起来最大就是 11？不对，第0间 + 第2间 + 第4间 = 2+9+1 = 12，所以答案是 12。

我刚才算的 dp[4] 是 12，是对的。完整路径是选下标为0、2、4的房间，它们两两不相邻，总金额12。可以看到，最终结果不是简单跳一间偷一间，而是动态调整的，这就是DP和贪心的本质区别。

2.2 最直观的实现：一维DP数组

理解了状态定义和转移方程，代码写起来几乎就是照着公式念一遍。这里我给出最直观的 Python 实现，用一个长度为 n 的数组记录所有中间状态。

def rob(nums): if not nums: return 0 n = len(nums) 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[-1]

这段代码的时间复杂度是 O(n)，空间复杂度是 O(n)。对于面试场景，这个版本已经能拿到满分了——逻辑清晰，易于解释。但如果你想更进一步，超越“能写出来”而达到“掌握”，那还得理解下面这个优化。

2.3 空间压缩：滚动变量取代整个数组

你仔细看递推公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，发现一个问题没有？要算出 dp[i]，根本不需要 dp[0] 到 dp[i-3] 这些更早的历史值，只需要 i-1 和 i-2 两个位置的结果。既然如此，何必用一整个数组把它们全存下来？两个变量滚动更新就足够了。

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

这里有朋友可能会问：prev2 和 prev1 的初始值为什么是 0？因为循环开始前还没有遍历任何房间，dp[-2] 和 dp[-1] 都视为 0，对应“没有房间可偷”的状态。循环开始后，第一次迭代读取 nums[0]，cur = max(0, 0 + nums[0]) = nums[0]，然后 prev2 变成 0，prev1 变成 nums[0]。第二次迭代读取 nums[1]，cur = max(nums[0], 0 + nums[1])，正好就是前两间房的最优解。整个滚动过程非常顺滑，不需要特判 n=0 或 n=1，因为空数组直接返回 0，单元素数组最终也会返回 nums[0]，边界问题被状态初始化天然消化掉了。空间复杂度降为 O(1)，代码反而更简洁。

这段代码我建议你当口诀一样背下来，因为打家劫舍 II 以及后面我讲的一系列变体，全都建立在它上面。

3. 打家劫舍 II：环形结构怎么破

3.1 环形和线性的本质差异

213题在198题的基础上加了一个条件：这些房子围成了一圈，也就是说第一间房子和最后一间房子现在也相邻了。这一加不要紧，直接把整个问题的结构改变了。在线性结构里，只有相邻的两两之间互相限制；环形结构里，首尾这两个原本八竿子打不着的房间，突然也有了约束关系。

这个约束带来什么后果？最直接的一点：你不可能同时偷第0间和第 n-1 间房。如果偷了第0间，第 n-1 间就必须放弃；如果偷了第 n-1 间，第0间就不能碰。这实际上把原来的一个完整问题，切割成了两个互斥的线性子问题：

• 不偷第0间：那么范围变成 nums[1:]，可以在下标 1 到 n-1 之间自由线性决策；
• 不偷第 n-1 间：那么范围变成 nums[:n-1]，可以在下标 0 到 n-2 之间自由线性决策。

取这两个子问题结果的较大值，就是整个环形场景的最优解。

你可能会问一个问题：为什么这样可以覆盖所有情况？我们来想一下。全局来看，无非两种可能：偷了第0间，或者没偷第0间。偷了第0间的话，根据环形规则第 n-1 间肯定不能偷，所以问题退化成在 nums[:n-1] 上的线性问题；没偷第0间的话，第 n-1 间可选可不选，完全看收益，所以问题退化成在 nums[1:] 上的线性问题。这两个子问题叠加，正好覆盖了所有可能的选择组合，不会有遗漏，也不会有重复计算。

3.2 复用线性逻辑的优雅实现

理解了上面的拆解，代码写起来就非常干净了。我直接复用上一节的滚动变量版本的 rob 逻辑，把它封装成一个内部函数，然后对两个切片分别调用，取最大值。

def rob(nums): if not nums: return 0 if len(nums) == 1: return nums[0] def rob_linear(arr): prev2 = 0 prev1 = 0 for num in arr: cur = max(prev1, prev2 + num) prev2 = prev1 prev1 = cur return prev1 return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

注意一个关键边界：当 nums 的长度为 1 时，nums[:-1] 是空数组，nums[1:] 也是空数组，两个 rob_linear 都会返回 0，直接取 max 会错误地得到 0。所以在调用前必须单独处理 len(nums) == 1 的情况，直接返回 nums[0]。这是我见过很多人在写这道题时摔的第一个跟头，先放进边界条件里解决掉，后面就顺畅多了。

这个版本的时间复杂度是 O(n)，因为两个子问题每个都要遍历约 n 个元素，加起来是 O(2n)，常数级别不影响量级。空间复杂度是 O(1)，依然很省。

我为这个环形拆解专门走一个例子，帮助你把过程彻底看透。设 nums = [2, 3, 2]，这是题目的官方示例。如果按线性逻辑跑 nums[:-1] = [2, 3]，结果是 max(2, 3) = 3，对应“不偷最后一间，偷中间那间3”；跑 nums[1:] = [3, 2]，结果同样是3，对应“不偷第一间，偷中间那间3”。两者取最大，答案是3。手动验证一下，由于首尾相邻，三间房里只能偷中间这一间，或者偷第0间和第2间？不行，因为第0间和第2间在环形里也是相邻的，所以只能偷一间，最大值是3，正确。

再看一个稍微复杂的例子，nums = [1, 2, 3, 1]。nums[:-1] = [1, 2, 3]，线性最优是选1和3，得4；nums[1:] = [2, 3, 1]，线性最优是选2和3？不对，2和3也相邻，只能是 max(2+1=3, 3+1=4, 2+3=5但相邻不可行)……我重新算，[2, 3, 1] 的线性最优是选择 2 和 1，得3；或者选择3，得3。所以第二个子问题是3。最终取 max(4, 3) = 4。对应原环形数组，选择下标0和2（1和3），首尾下标0和3不相邻（因为圆环里它们相邻，所以下标0和2不相邻，下标0和3相邻不行），总金额4，正确。

3.3 两种常见拆解写法对比

我在很多题解里看到不同的写法，有人直接写两个循环，有人封装函数，还有人用取模模拟环形。这里我说说我的看法。直接写两个循环的好处是省去函数调用的开销，但代码重复度高、逻辑冗余；封装内部函数的好处是结构清晰，复用性强，后续如果要处理多个类似的子问题，改动最小；取模模拟环形看着酷炫，但实现起来需要额外处理索引映射，反而容易出错。我个人的建议是，在面试和日常刷题中优先选择封装内部函数的写法，它让阅读代码的人一眼就能看出“我把环形拆成了两个线性问题”，沟通成本最低。

顺便提一个进阶版本的写法。如果你不想写两个循环，也可以用取模的方式遍历两次，但只执行到第二次遍历结束。不过说实话，这种优化在简单题上没有太大必要，属于面试加分的“sugar”，不是核心考点。真正的考点在于你能否敏锐地识别出环形结构导致的首尾互斥关系，并给出拆解方案。

4. 踩坑实录：常见问题与排查技巧

4.1 状态定义不清引发的边界错误

最常见的一个错误，是把 dp[i] 理解成“一定偷第 i 间房的最大金额”。如果沿着这个错误定义往下推，你会发现 dp[i] = nums[i] + max(dp[i-2], dp[i-3])，需要额外记录 dp[i-3]，状态转移变得复杂，还容易漏掉“两个相邻房间都不偷”的情况。而正确的定义是“考虑前 i 间房这个范围的最大金额”，不需要强制选第 i 间，转移方程自然简洁，也不会漏状态。

我建议你在动手写代码之前，先在注释里写下两句话：dp[i] 代表什么？dp[i] 怎么由更小的子问题得到？如果能用自然语言把这两句话讲清楚，代码基本不会写错。

4.2 环形场景遗漏边界特判

打家劫舍 II 里最常见的错误就是没有处理 len(nums) == 1 的情况。很多人的代码是直接 return max(rob(nums[:-1]), rob(nums[1:]))，然后面对单元素输入返回 0，直接满盘皆输。我自己在 LeetCode 上第一次提交就栽在这里，所见即所得地拿到一个 WA。排查方法很简单，就是要强制自己思考：当数组长度为 0 和 1 时，我代码里每一个切片和索引是否还成立？

4.3 滑动窗口或排序思路的误入

还有一类朋友，看到“不能相邻”就联想到“隔一个取一个”，于是试图用排序或者贪心间隔的思路去解。比如有人会想：把所有金额从大到小排序，然后逐个检查是否相邻，如果相邻就跳过。这个思路的问题在于，排序会丢失原始位置关系，而且“跳过一个大房子换来两个中等房子”的情况是排序无法建模的。还是上面那个例子 [2, 1, 1, 2]，排序后变成 [2, 2, 1, 1]，贪心选两个2，但它们在原始数组中恰好相邻，直接翻车。

要根治这个误区，你要真正理解：相邻约束本质上是“位置上的约束”，不是“金额上的约束”。所有需要依赖原始位置顺序的问题，都千万不要先排序，这是算法题里的铁律之一。

4.4 排查思路速查表

如果你写出来的代码结果不对，我整理了一个常用的排查顺序，按这个顺序逐项检查，基本能覆盖90%的问题：

手动算一遍中间值这个习惯，我到现在刷题都还在用。别嫌麻烦，DP题的 bug 用肉眼很难看出来，但一行一行对比手算结果时，往往几秒钟就能定位到问题出在第几次迭代。

5. 从两道题延伸出去的DP解题框架

5.1 识别动态规划题目的信号

如果你刷题时经常不知道一道题该不该用DP、该怎么定义状态，可以试试这个三步判别法。第一步，看题目是否具备重叠子问题——比如“偷前 i 间的最大金额”会被后面多个更大的子问题重复用到；第二步，看是否有最优子结构——即局部最优组合能否构成全局最优；第三步，看状态是否能通过少数前驱状态递推得出——如果发现某个位置的结果只需要前面一两个位置的结果，那大概率是DP。

拿打家劫舍来说，不用递归就是因为它的递推关系非常线性，子问题之间没有交叉依赖的复杂图结构，用循环自底向上填充即可。它整个思考路径特别适合用来训练DP思维的“肌肉记忆”：定义状态 → 找转移方程 → 设初始值 → 确定遍历方向 → 压缩空间。

5.2 打家劫舍系列的题型拓展

LeetCode 上打家劫舍其实有三连，一题是 linear（198），一题是 circular（213），还有一题是 binary tree（337）。337题“打家劫舍 III”把一维数组换成二叉树结构，相邻约束变成了“父子节点不能同时偷”，状态定义也随之变成每个节点上选或不选两种状态，用树形DP做后续遍历。如果你已经吃透了198和213，337题其实就是把线性的两个滚动变量，换成递归返回的二元组 (不偷当前节点的最大金额, 偷当前节点的最大金额)。这个系列帮你打通线性DP、环形DP和树形DP三条线，性价比极高。

我当时刷完三道题之后有过一个体会：它们表面上都是“不能相邻”，但思考的颗粒度完全不同。198要求你理解一维数组的自底向上填充，213要求你学会把环形约束拆成线性区间，337要求你把“状态”从单个数值扩展成结构体。从易到难、从线性到非线性，每一层都正好考一个独立的DP技能点，难怪这个系列是各大刷题清单的常客。

5.3 面试现场如何快速写出满分答案

面试如果碰到原题，不需要一开始就跳到最优解。我建议的顺序是：先说出暴力递归思路，分析出有大量重复子问题；然后引出DP数组解法，写出一维版本；最后说“这个递推只用到了 i-1 和 i-2 两个状态，所以可以压缩到两个变量”，顺手改写滚动变量版本。这个从暴力到DP再到优化的演进过程，本身就是面试官最想看到的思考链，比你直接甩出最优解更有说服力。如果是环形版本，在完成线性版本之后，补一句“环形会引起首尾互斥，所以拆成两个线性区间分别求解，再取最大值”，这一段话足以展示你对环形DP的理解深度。

这两个题做完，我强烈建议你立刻做一道同类但完全不同的题练手，比如“按摩师”（面试题 17.16）或者“粉刷房子”（LintCode 515）。它们和打家劫舍形态相似但约束条件有差异，能帮你检验自己是真懂了DP框架，还是只记住了这一题的代码。我个人的经验是，把dp[i] = max(dp[i-1], dp[i-2] + nums[i])这个核心公式理解到“滚瓜烂熟”的程度，胜过盲目刷十道重复题。动态规划的知识点就那么几个套路，真正拉开差距的不是刷题数量，而是你把每个套路的边界条件和变换方式掌握得有多精确。