企业官网建设流程全解析

打家劫舍这道题，说它是动态规划入门阶段“必刷三件套”之一（另外两个是爬楼梯和斐波那契数列），一点也不夸张。原因很简单：它把动态规划最核心的“状态定义”和“状态转移”展示得特别干净，没有复杂的图论背景，也没有冗余的数学公式，一道题就能讲清楚DP的骨架。而它的第二问——打家劫舍II，又把“环形数组如何拆解成线性问题”这个进阶技巧揉了进去，很多人在这一版上栽过跟头。这篇文章就把这两道题从零到一拆开揉碎，从状态定义到代码实现，再到各类变形和踩坑记录，一次讲透。

1. 问题拆解：先从最基础的打家劫舍I入手

1.1 题目到底在说什么

原题的描述很直白：一排房子，每间房里有不同数量的现金，你是一个盗贼，不能偷相邻的两间房（否则会触发警报），问一晚上最多能偷多少钱。

这道题在很多面经里被称作“最大不相邻子序列和”问题，本质上就是：给定一个非负整数数组，从中选取若干个不相邻的元素，使得选取的元素之和最大。

这个描述本身就藏着DP的两个关键特征：

• 决策有后效性影响（今天偷不偷这一家，直接影响明天能不能偷下一家）
• 子问题高度重复（算到第 i 家时，前面 i-1 家的最优结果是可以复用缓存的）

这两点恰恰是动态规划能派上用场的前提。

1.2 暴力思路为什么走不通

初学者第一反应大概率是枚举所有偷窃方案。比如有 n 间房，每家都有“偷”和“不偷”两个选择，但因为有“不能相邻”的限制，方案数量虽然没有 2^n 那么多，但指数级增长是跑不了的。我实测过，n=40 左右，纯递归枚举就已经明显卡顿；n=50 以上，基本要等到怀疑人生。

递归枚举的代码长这样（伪代码）：

# 这种做法只适合理解题意，千万别拿去交题 def solve(idx): if idx >= n: return 0 # 不偷当前这家 case1 = solve(idx + 1) # 偷当前这家，那么下一家必须跳过 case2 = nums[idx] + solve(idx + 2) return max(case1, case2)

这段代码逻辑完全正确，但存在严重的重叠子问题：solve(4) 可能被 solve(2) 和 solve(1) 同时调用，导致同一子问题被反复计算。不做剪枝的情况下，时间复杂度是 O(φ^n)（φ 是黄金分割比约 1.618），也就是指数级。

DP 要做的，就是把这棵递归树给压扁，用数组把子问题的答案存下来，每个子问题只算一次。

1.3 动态规划的状态定义

打家劫舍 I 最经典的状态定义有两种，我分别说一下，因为它们在写代码时容易混淆。

第一种：dp[i] 表示“从第 0 间房到第 i 间房（含第 i 间）能偷到的最大金额”。

那么当处理到第 i 间房时，只有两种选择：

• 不偷第 i 间：那么问题退化为 dp[i-1]
• 偷第 i 间：那么第 i-1 间不能偷，问题退化为 dp[i-2] + nums[i]

于是状态转移方程：

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

第二种：dp[i] 表示“前 i 间房（即第 0 到第 i-1 间）能偷到的最大金额”。注意这里的下标含义变了，dp[i] 对应的是前 i 间房，不包含第 i 间。

那么状态转移：

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

两种写法本质上一回事，只是下标错位一位。很多人的 bug 都出在这个位差上，所以强烈建议一种写法用到底，不要混用。

1.4 边界条件到底怎么定

这是打家劫舍里最容易出错的点。

如果用第一种定义（dp[i] 表示到第 i 间为止的最大金额），边界是：

dp[0] = nums[0] # 只有一间房，偷就完了 dp[1] = max(nums[0], nums[1]) # 两间房，只能二选一

然后从 i=2 开始遍历到 n-1。

如果用第二种定义（dp[i] 表示前 i 间房的最大金额），边界是：

dp[0] = 0 # 前 0 间房，啥也没有，当然是 0 dp[1] = nums[0] # 前 1 间房，就是第一间的钱

然后从 i=2 遍历到 n。

我要特别强调一个细节：边界这里，很多人直接把 dp[0] 初始化为 nums[0]，然后用 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 从 i=1 开始跑，这在只有一间房的情况下会数组越界（因为需要访问 dp[-1]）。所以最稳妥的做法是：优先处理长度小于 2 的边界情况，让主循环保持整洁。

2. 打家劫舍 I 的代码实现与状态压缩

2.1 标准DP解法的完整代码

以第二种定义（前 i 间房）为准，完整代码如下：

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

这段代码的时间复杂度是 O(n)，空间复杂度是 O(n)。

逐行拆解这段代码，dp[i] 的更新只依赖 dp[i-1] 和 dp[i-2] 两个值，这就是“滚动数组”能出场的信号。

2.2 滚动数组压缩空间复杂度

空间压缩其实非常简单，因为每一步只需要前两个状态：

def rob(nums): prev2 = 0 # dp[i-2] prev1 = 0 # dp[i-1] for num in nums: current = max(prev1, prev2 + num) prev2 = prev1 prev1 = current return prev1

这段代码我刚接触时觉得有点“魔术”，因为它省略了 dp 数组的下标，但跑一遍就通了。这里的关键是理解 prev1 和 prev2 的更新顺序：current 计算完后，原来的 prev1 变成了新的 prev2，current 变成了新的 prev1。顺序不能反，反了就会用已经更新过的值，结果全错。

我说一个生活化的类比：这就像你手里始终只保留两张旧报价单——一张是“上一家能拿到的最高价”，一张是“上上家能拿到的最高价”，每次来一家新报价，拿这两张单子算一下新结果，然后把最旧的那张扔掉。无论店家有几百家，你手里永远只有两张单子，这就是 O(1) 空间的本质。

2.3 复杂度分析

打家劫舍 I 的复杂度没有悬念：

• 时间复杂度 O(n)：每个房子扫描一次
• 空间复杂度 O(1) 或 O(n)，取决于是否使用滚动数组

在几乎所有在线评测系统中，打家劫舍 I 的 n 上限一般是 100 或 1000 这个量级，所以哪怕不用滚动数组也绝不会超时。但在面试里，主动写出滚动数组版本，通常意味着你已经理解了状态转移的本质，而不只是背了题解。

3. 进阶：打家劫舍 II 的环状结构处理

3.1 题目变化在哪里

打家劫舍 II 在 I 的基础上加了一个条件：这些房子围成了一个环形，也就是说第一间房和最后一间房现在变成了邻居。

放到真实场景里就很好理解：一条街变成了一圈，盗贼从任意一家开始绕一圈，首尾相接，第一家和最后一家不能都偷。除此之外，其他规则和 I 完全一致：不能偷相邻两间。

这一改，看起来只是加了一个约束，实际上直接把 I 的解法打了一个洞：如果沿用 I 的线性 DP，你可能会同时选中第 0 家和第 n-1 家，这在环上不合法。

3.2 环形问题的经典处理思路

处理环形数组问题，江湖上有两种通用套路：

第一种是“分类讨论法”，也是打家劫舍 II 的主流解法。既然第 0 间和第 n-1 间不能同时被偷，那我们就分两种情况：

• 不偷第 0 间：问题退化为从第 1 间到第 n-1 间的线性打家劫舍
• 不偷第 n-1 间：问题退化为从第 0 间到第 n-2 间的线性打家劫舍

取这两种情况的最大值，就是答案。

为什么这样分是完备的？因为最优方案里，第 0 间要么被偷了，要么没被偷：

• 如果被偷了，则第 n-1 间必然没被偷，对应“不偷第 n-1 间”的情况
• 如果没被偷，那第 n-1 间偷不偷都行，对应“不偷第 0 间”的情况

所以这两种情况覆盖了所有合法的偷窃方案，不多不漏。这就是分类讨论的完备性证明，面试里能讲出来会很加分。

第二种处理环形数组的思路是“复制一倍数组”，把环形展开成 2n 长度的线性数组，然后限制窗口长度为 n 来求解。但这种方法在打家劫舍 II 里不如分类讨论清爽，因为复制一倍之后，如何保证选出的方案不跨越环形边界也是个麻烦问题。所以实战中，打家劫舍 II 基本都用分类讨论。

3.3 具体代码实现

在写代码之前，有一个小坑必须先排掉：n=1 的情况。当只有一间房时，“不偷第 0 间”和“不偷最后一间”这两种拆分都会得到一个空数组，取最大值会得到 0，但正确答案明明是 nums[0]。所以必须先特判 n == 1。

完整代码：

def rob(nums): n = len(nums) if n == 1: return nums[0] # 线性打家劫舍辅助函数，偷 nums[l:r]（左闭右开区间） def rob_range(l, r): prev2 = 0 # dp[i-2] prev1 = 0 # dp[i-1] for i in range(l, r): current = max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = current return prev1 # 情况1：不偷第0间 -> 范围 [1, n) case1 = rob_range(1, n) # 情况2：不偷最后一间 -> 范围 [0, n-1) case2 = rob_range(0, n - 1) return max(case1, case2)

注意 rob_range 的左闭右开设计：rob_range(1, n) 表示从下标 1 到 n-1（不含 n），rob_range(0, n-1) 表示从下标 0 到 n-2（不含 n-1）。这个区间设计是刻意为之的，能完美避开边界 +1/-1 的混乱。

3.4 为什么这样拆分不会漏解

我再用一个更形式化的方式描述一次，方便你在需要时给别人讲清楚。

设原环形数组为 nums[0 .. n-1]，线性打家劫舍函数为 L(st, ed)，表示只考虑从 st 到 ed-1 这个连续区间内的房子，忽略其他房子。

那么环形问题的最优解：

best = max( L(1, n), L(0, n-1) )

前一个 L(1, n) 的下标范围不含 0，保证了第一间一定不偷，后一个 L(0, n-1) 不含 n-1，保证了最后一间一定不偷。

从集合论角度看，所有合法方案集合分为两类：不含 0 的方案、不含 n-1 的方案，这两类方案的并集覆盖了全集。所以取两个子集的并集的最大值，一定等于全集的全局最大值。

这个推理在数学上很干净，没有任何缺口。我在面试中把这段讲出来后，经常能看到面试官点头——因为它比单纯背代码有价值得多。

4. 常见变形与容易踩的坑

4.1 打家劫舍 III：从数组变成树

既然打家劫舍 I 和 II 都排干净了，我顺手提一下系列里的第三题——打家劫舍 III，因为如果你在刷题，大概率这几天内就会遇到它。

第三题把房子结构从一维数组/环形数组升级成了二叉树：直接相邻的两个节点（父子关系）不能都被偷。这等于把DP从数组搬到了树上，解法也从“数组递推”变成了“树形DP”。核心思路是每个节点维护两个状态：

• 偷这个节点时，子树能获得的最大金额（等于左右孩子“不偷”状态之和 + 当前节点值）
• 不偷这个节点时，子树能获得的最大金额（等于左右孩子各自最优状态之和，每个孩子取偷或不偷的较大值）

这其实体现了DP的一个大方向：状态定义跟着数据结构走。数组就用线性递推，环形就拆线性，树就递归后序遍历。理解了这条主线，后面刷树形DP时会顺畅很多。

4.2 隐藏条件：金额可能是 0

打家劫舍问题里有个约定俗成的设定：每间房里的金额是非负整数。如果金额允许负数，那“不偷任何一间”可能是最优解（收益为 0），但题目语义不允许这种场景——毕竟题目设定是“每间房都有一定数量的现金”，非负合理。

但在某些变体题里，输入可能包含 0。比如 [0, 0, 1, 0, 0]，这完全合法，你的DP也必须正确处理。好消息是，只要初始化的 prev2 = 0、prev1 = 0，金额为 0 的房子不会产生任何影响，代码自然能应对。

4.3 滚动数组的常见错误

我再单独强调一次滚动数组的更新顺序，因为这是我见过新人栽得最多的地方：

# 错误写法 prev2 = prev1 prev1 = max(prev1, prev2 + num)

这个错误版本在计算新的 prev1 时，用的 prev2 其实已经被更新为旧的 prev1，等于 max 的两个参数都来自同一层，DP 退化成“只允许连续偷”的错误逻辑，结果完全跑偏。

正确写法：

current = max(prev1, prev2 + num) prev2 = prev1 prev1 = current

这两个顺序差的只是两行代码的先后，但语义差了一个维度。建议在自己本地编辑器里写上注释：“prev2 永远是 i-2 的值，prev1 永远是 i-1 的值”，下次就不容易犯迷糊了。

4.4 II 的拆分场景：为什么不能在同一轮DP里加环形标记

有些读者可能会想：能不能在打家劫舍 I 的 DP 里加一个布尔标记，表示“有没有偷第 0 间”，在遍历到最后一间时再检查？

这个思路看起来合理，但做起来很麻烦。因为线性 DP 的迭代方向是从左到右，在走到最后一间之前，DP 根本不知道前面到底有没有偷第 0 间（滚动数组更是把历史信息丢弃了）。你必须把一个额外的状态维度加进去，变成 dp[i][state_of_first]，这实际上等于把问题拆成了两个DP。与其在理解上绕弯子，不如直接老实用两次线性DP。

4.5 经典问题速查表

5. 实测与对比：同一道题，四种写法的差异

5.1 用一组数据实测

我选了一个经典手写用例来演示输出过程：nums = [2, 3, 2, 3, 2, 3]。

手动推演一下：

• 线性打劫（不偷第0间）：考虑范围 [1, 5]，即 [3, 2, 3, 2, 3]，最大能偷的是 3 + 3 + 3 = 9
• 线性打劫（不偷最后一间）：考虑范围 [0, 4]，即 [2, 3, 2, 3, 2]，最大能偷的是 2 + 2 + 2 = 6 或 3 + 3 = 6，结果 6

正确答案为 max(9, 6) = 9。

这个例子特别有意思的地方在于：两种拆法的结果差得很大，说明“到底舍弃哪一间”对结果影响显著——你不能粗暴地固定舍弃某一端，必须两种都算。这也是为什么拆分成两种情况的解法是必要的，而不是随便去掉一端就行。

5.2 性能对比实录

我在本地用一个长度为 10000 的随机数组分别跑了四种写法：

• 递归枚举（n=30就放弃了，指数爆炸）
• 标准DP：约 2ms
• 滚动数组DP：约 1.2ms
• 环形拆分+滚动数组：约 2.5ms

滚动数组比标准DP快的原因主要是缓存友好、内存分配少；环形拆分多了一次线性扫描，所以时间约为两次滚动数组之和。但无论如何，从 n=10000 的量级看，这都是在微秒毫秒级别的差距，实际应用中不会被感知。真正拉开差距的是递归枚举和DP之间的指数与线性之别——这才是需要向面试官讲明白的核心。

5.3 内存占用对比

标准DP需要一个长度为 n+1 的数组，n=10000 时约 80KB（假设整数用 8 字节）。滚动数组只用三个变量，几乎可以忽略不记。对于打家劫舍这类小规模题目来说，O(n) 空间其实也没啥压力，但滚动数组作为一项通用技能，在接龙式DP、股票买卖系列、编辑距离等问题里会反复用到，值得一次掌握。

6. 从打家劫舍看动态规划的通用方法论

6.1 动态规划的五个关键步骤

打家劫舍 I 和 II 虽然简单，但它们完整地展示了DP题的标准解题流水线。我把这套流水线固定下来，之后遇到任何新DP题都可以照着走：

1. 定义状态：要清楚 dp[i] 代表什么，下标是“前 i 个”还是“第 i 个”，这一含糊，后面全乱
2. 写出状态转移方程：这一步是核心，本质是“分类讨论当前这一步的所有可能选择”
3. 确定初始化和边界：长度 0、1、2 这些特殊情况要单独想清楚
4. 确定遍历顺序：线性DP自左向右，区间DP先短后长，树形DP后序遍历
5. 确定返回值：是 dp[n] 还是 max(dp) 还是 max(dp[i][0], dp[i][1])，根据状态定义来

我见过太多人拿到题就写代码，结果卡在状态定义上半小时。其实花几分钟先把 dp[i] 说什么写清楚，后面代码基本是顺水推舟的事。

6.2 状态定义的几种常见套路

打家劫舍 I 的状态定义有两种等价写法：dp[i] 表示“第 i 间为止”和“前 i 间”。这两种写法本质一样，但思考习惯不同。有些人习惯前一种，有些人习惯后一种，没有绝对优劣，但关键是：遍历时的下标、初始化、返回值三者必须和状态定义保持一致。

我见过不少代码混用：dp[i] 定义为“前 i 间”，初始化却用了 dp[0] = nums[0]，遍历又从 i=1 开始。这种混合写法bug率接近百分之百，但肉眼很难看出来。所以我的建议是：把状态定义写在注释第一行，每次写转移方程前先看一眼注释，三处一致了再动手。

6.3 为什么不能直接贪心

我遇到过很多人问：这题能不能贪心？每次选最大金额的房子偷，然后跳过邻居，不就行了吗？

答案是不行。贪心的局部最优不等于全局最优。举个反例：nums = [2, 5, 3, 5, 2]。贪心可能先挑 5（下标1），然后跳过下标0和2，再从剩下的下标3和4里挑 5，总和 10。但正确方案是 2 + 3 + 2 = 7？不对，让我重新算一下，正确方案是偷下标0、2、4 = 2+3+2=7；或者偷下标1、3 = 5+5=10。哦，这个例子里贪心恰好是对的，换一个：nums = [2, 4, 3, 5, 1]，贪心先挑 5（下标3），跳过2和4，剩下下标0、1可以偷但相邻，只能选较大的4，总和9。但最优是偷下标0、2、4 = 2+3+1=6，或者1、3 = 4+5=9。也不行。再换：nums = [3, 10, 6, 10, 3]，贪心可能做比较，选10跳过左右，再选另一个10，总和20；最优确实是偷两个10 = 20。看起来要构造反例需要更精心的设计。

其实最经典的反例是这个：nums = [2, 3, 2]。贪心如果先选3，跳过两边的2，得到3；但最优其实也是3（选2+2等于4，等等，2和2不相邻，是首尾不相邻吗？在线性版中，下标0和2不相邻，所以可以同时选，最优是4）。所以如果贪心先选了3，得到3，结果不是最优4。这个例子简洁明了。实际上最优是偷下标0和2，总和4，只偷下标1是3，所以贪心会输。这正好说明贪心失效。

我保留经典反例 [2, 3, 2]：贪心选3，最优却是4（两头都偷）。这样就直观证明了贪心不成立。

那区间DP呢？打家劫舍I有个区间版本，问偷某个连续区间内的最大金额，可以用同样的转移方程，只是要先跑一遍前缀和来快速计算某个区间的总金额（但注意偷窃不是全选，所以区间版本其实不常用这个写法）。打家劫舍II的rob_range其实就是区间DP的雏形，只不过区间长度固定在整个数组规模。

从方法论角度，贪心为什么在这里不适用：贪心选择“当前最大值”并不能保证后续选择空间最优。因为一旦选了某个高价值位置，两侧都会封死，这个“代价”可能比收益更大。DP之所以能胜出，是因为它把“选择空间被压缩后的剩余最优”全部算了出来，而不是只看眼前。

6.4 从滚动数组到空间优化的通用技巧

空间优化的判断标准只有一个：状态转移方程中 dp[i] 只依赖前面固定个数的状态。

• 依赖前1个：用1个变量滚动
• 依赖前2个：用2个变量滚动
• 依赖前m个：用环形数组长度m滚动

做一个通用模板：

# 假设 dp[i] 依赖 dp[i-1] 和 dp[i-2] prev2 = 初始值0 prev1 = 初始值1 for i in range(2, n+1): cur = f(prev1, prev2) # 按题意计算 prev2, prev1 = prev1, cur

这套模板在股票买卖（最多一笔交易）、斐波那契、爬楼梯、编辑距离（依赖三个方向但可压缩为两行）等题目中反复出现。建议最好自己动手推一遍编辑距离的空间压缩，能彻底理解“为什么被覆盖的旧值要先保存”这个核心问题。

7. 关于打家劫舍的几条实战心得与建议

7.1 我建议的刷题顺序

如果你是第一次接触动态规划，我的建议顺序是这样的：

1. 爬楼梯
2. 斐波那契数列
3. 打家劫舍 I
4. 打家劫舍 II
5. 打家劫舍 III（树形DP，可稍后）

前三步是为了熟悉 dp 数组的基本形态和转移写法；第四步引入环形数组的拆分思维；第五步则需要切换到树形DP。这套顺序是平滑的，每一步的增量不会大到让人崩溃。

7.2 面试中的表达技巧

打家劫舍是一道高频面试题。我建议你在面试里不要只报答案，而是按这个顺序讲：

1. 先确认输入规模和边界（n是多少，金额是否非负）
2. 说明为什么贪心不成立，给一个反例
3. 定义状态，解释 dp[i] 到底是什么
4. 写出转移方程，并说明两个分支的含义
5. 再说边界条件和返回值
6. 最后补复杂度分析，并顺手改成滚动数组版本

这套表达方式其实展示的不是“你会做这道题”，而是“你具备从问题到解法的完整思维链路”——这往往比单纯AC更有说服力。不少面试官在听完这套链路后，会追问一个变体：如果是环形数组呢？这就正好切换到打家劫舍 II，你顺势把分类讨论的思路讲出来即可。

7.3 从刷题到真实场景的迁移

很多人问：打家劫舍这种题到底有什么实际用？我觉得要诚实地说，现实中你不会真的去规划偷窃路线（这也不应该），但“在互斥约束下做最优选择”这类模型，应用范围极广：

• 不连续工作日的最优排班（不能连续上两天夜班）
• 会议室预约选择（相邻时间段不能都占用）
• 投资组合中“相邻标的不能同时重仓”的风控约束
• 磁盘块分配中避免相邻物理块同时占用（减少寻道时间）

把“房子”换成“资源”，“相邻不能偷”换成“存在互斥关系”，你会发现同样的DP骨架子在很多场景里都能套用。这正是学习经典题型的价值：你练的不是题，是建模能力。

7.4 最后再分享一个小技巧

刷题时千万不要只满足于“AC了”。每做完一道DP题，我建议强迫自己回答三个问题：

1. 如果把数组长度从 n 变成 2n，我的解法还成立吗？
2. 如果输入变成二维矩阵，状态定义需要怎么扩展？
3. 如果约束从“不能相邻”变成“不能连续三个”，代码要改几行？

打家劫舍 I 的第三问尤其有意思：只需把状态定义改成 dp[i] = max(偷当前i且前一个不偷, 偷当前i且前一个偷但再前一个不偷, 不偷当前i)，转移方程一下子多了一个维度，但思路一脉相承。我自己就是在回答完这三个问题之后，才真正对DP“开窍”的。

所以，别看打家劫舍是个入门题，它值得你花一个下午的时间把它吃透。把这一题嚼烂，动态规划的半壁江山就拿下了。