企业官网建设流程全解析

刷 LeetCode Hot 100 的人，几乎没人能绕开“打家劫舍”这道题。它挂在动态规划专题下的位置很微妙——说简单吧，第一次接触的人很容易被“相邻不能同时偷”这个约束绕晕；说难吧，它又不涉及背包、区间、状态压缩这些高级模型。我刷这道题的时候已经在面试中被问过三次，每一次都能从这题里延伸出不同的考法：要么改成环形数组，要么改成二叉树结构，要么套一层“先转化再DP”的壳。可以说，把它彻底吃透，等于同时拿下了 DP 入门、空间优化和变种迁移三样基本功。

这篇文章我会从最朴素的解题思路讲起，把状态定义、递推公式、滚动变量优化、边界条件这些硬核内容全部拆开揉碎，再把环形数组、树形 DP、值域映射这些经典变种一起串联起来。适合正在刷 Hot 100 准备面试的求职者，也适合想系统打一遍动态规划基础、不想只会背模板的人。代码会用 Python 写，思路部分尽量做到不依赖语言，你用 Java、C++ 也能直接平移。

1. 题目画像：Hot 100 里“入门即巅峰”级别的 DP

1.1 原题描述与核心限制

题目给的是一个非负整数数组，每一格代表一间房子里的现金数量。你是一个专业盗贼，要沿街偷窃，唯一规则是：不能同时偷相邻的两间房子，否则会触发报警。问能偷到的最大总金额是多少。

这个约束是整道题的命门。它意味着你面对每一间房子时只有两种选择：偷它，则必须跳过下一间；不偷它，则下一间照常独立决策。难点不是“偷哪个”，而是“偷法”必须在所有相邻组合之间做一个全局最优的取舍。

1.2 为什么这道题能占据 Hot 100 一席

表面上它只是一个简单的一维线性 DP，但它的代表性恰恰在于“最经典的入门模型”。面试官喜欢它，是因为它能在十分钟内考察出候选人三件事：能不能识别出重叠子问题、能不能准确写出状态转移、能不能在常量空间内完成优化。这三件事恰好是动态规划最核心的能力圈。相比斐波那契数列，它有真实的业务场景包装；相比背包问题，它不需要二维状态就能讲清思路。所以它既是 Hot 100 的常客，也是很多题库里动态规划专题的第一道题。

1.3 贪心为什么在这里行不通

很多人看到这道题第一反应是“隔着偷就行”，甚至有人会尝试“先按金额排序，再跳着取”。这两种思路全是坑。排序会直接破坏相邻关系，跳着取则忽略了“连续跳过两间”甚至“跳过三间”可能才是更优解。可以拿一个反例：金额序列[2, 1, 1, 2]，如果按“隔一个偷一个”的思路从第一个开始偷，得到金额是 2 + 1 = 3，但实际上偷第 1 间和第 4 间，能拿到 4。所以这类题目只能老老实实做决策搜索，也就是动态规划。贪心只在每一步的选择与全局最优一致时才成立，而这里“眼前最大的金额”完全不代表“最终收益最大”，这也是我后来做题时反复提醒自己的：遇到相邻约束，先别急着排序，先想想状态怎么走。

2. 从暴力递归到状态定义：递推公式是怎么长出来的

2.1 先写出“能跑但很慢”的做法

动态规划不是一拍脑袋就来的。最自然的起点是暴力递归：从第一间房子开始，对每一间屋子做“偷 / 不偷”两个分支。偷了当前这间，下一步只能跳到i + 2；不偷当前这间，下一步走到i + 1，把两条分支计入的最大值返回上来。写成代码大概长这样：

def rob(nums): def dfs(i): if i >= len(nums): return 0 # 偷 i：累加当前金额，跳到 i+2 steal = nums[i] + dfs(i + 2) # 不偷 i：跳到 i+1 skip = dfs(i + 1) return max(steal, skip) return dfs(0)

这段代码思路完全正确，但时间复杂度是 O(2^n)——每个位置都有两个分支，指数爆炸。我初学的时候就觉得“暴力解都写出来了，正解还会远吗”，事实也确实如此，只需要观察递归树里是否存在大量重复计算。

2.2 重叠子问题：性能瓶颈的真正来源

手动模拟一下dfs(0)会调用dfs(2)和dfs(1)，而dfs(2)又会调用dfs(4)和dfs(3)，dfs(1)会调用dfs(3)和dfs(2)。注意看，dfs(2)在dfs(0)和dfs(1)两条分支里都被计算过，dfs(3)同理。这些重复计算就是重叠子问题。

要解决它，要么加一个缓存（记忆化搜索），要么把递归过程反过来，自底向上填表。后者就是真正意义上的动态规划。自底向上的好处是省去了递归栈开销，也让转移顺序变得直观：要算dp[i]，只需要知道dp[i-1]和dp[i-2]，从前往后推就行。

2.3 状态定义与转移方程：从“前 i 间”开始

最常见也最稳的状态定义是：用dp[i]表示从前 i 间房子（下标 0 到 i-1）中能偷到的最大金额。注意这里我特意用了“前 i 间”而不是“第 i 间”，因为这样才能把边界写干净：dp[0] = 0表示一间房子都不偷，dp[1] = nums[0]表示只考虑第一间。接下来处理第 i 间（下标 i-1）时只有两种情况：

• 不偷这间：结果等于dp[i-1]
• 偷这间：结果等于dp[i-2] + nums[i-1]，因为不能偷它的前一间

取两者中较大的那个就是最优值。写成公式就是：

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

这个公式就是整道题的灵魂。第一次看到的人可能会疑惑：为什么要额外考虑dp[i-1]而不是直接max(dp[i-2] + nums[i-1], ...)？因为不偷当前这间时，前 i-1 间的最大收益可能是偷第 i-2 间得到的，也可能是偷更前面、甚至连续跳过好几间得到的，dp[i-1]本身已经涵盖了所有这些情况。状态定义之所以选“前 i 间”，就是为了让这种历史最优值可以被直接复用。

3. 三种基础实现盘点：从数组到滚动变量的进化

3.1 一维 DP 数组版：最直观、最好讲

有了递推公式，代码就是一页纸：

def rob(nums): n = len(nums) if n == 0: return 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)。它的价值在于逻辑透明，面试时用来讲思路完全没问题。但既然题目只要求最大金额，不要求输出偷了哪些房子，我们完全有空间把空间复杂度降到 O(1)。

3.2 滚动变量优化：从数组退化成三个数字

观察递推公式会发现，计算dp[i]只需要前两个状态dp[i-1]和dp[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

这段代码的巧妙之处在于循环中每个num就是当前待决策的房子，prev1代表不含当前房子的前序最优，prev2代表跳过当前房子的前序最优。cur的新值要么沿用prev1（不偷），要么累加prev2 + num（偷）。很多人第一次看这版代码会愣一下，但只要对照数组版就能发现只是换了变量名而已，本质完全一样。我在实际面试中更推荐先写数组版，再口头补充“可以优化成两个滚动变量”，这样既展示正确性，又展示优化意识。

3.3 记忆化递归：另一种消除重复计算的方式

如果你更喜欢自顶向下的思考方式，记忆化搜索也很自然。只需要在暴力递归里加一个memo数组：

def rob(nums): n = len(nums) memo = [-1] * n def dfs(i): if i >= n: return 0 if memo[i] != -1: return memo[i] memo[i] = max(dfs(i + 1), nums[i] + dfs(i + 2)) return memo[i] return dfs(0)

这个版本的时间复杂度 O(n)，空间复杂度 O(n)（递归栈加缓存）。它更适合用来讲解“为什么暴力会慢”以及“缓存为什么能解决重复计算”这个演进过程。刷题时我习惯三种写法都会，面试时根据对方问法选择展示哪一种。如果对方从暴力切到优化，我就按“暴力 -> 记忆化 -> 动态规划 -> 滚动变量”这条线讲，逻辑非常顺。

4. 边界条件与易错点：这些坑我踩过不止一次

4.1 空数组与单元素的处理

nums为空时，能偷的最大金额自然是 0；只有一间房子时，最大金额就是nums[0]。这两条很容易被忽略，尤其是空数组。常见的错误是代码里dp[1] = nums[0]这行在空数组下直接越界，所以必须在函数开头做if not nums: return 0的判断。单元素情况在一些变种题里更值得警惕，比如环形数组版本，处理不好会在取子数组时得到空数组。

4.2 相邻约束导致的“不偷最大值”陷阱

决策时最容易犯的错误是把dp[i-1]想当然地理解成“必须偷第 i-1 间”。实际上dp[i-1]可能来自“偷第 i-2 间而不偷第 i-1 间”，也可能来自“第 i-1 间之前的好几个都不偷”。正是因为这个定义覆盖了多种偷法，才有递推的简洁。如果理解不了这一点，建议回到暴力递归状态：dp[i-1] = max(偷第 i-1 间, 不偷第 i-1 间)，它本来就是一个已经做完决策的全局最优值，不受当前第 i 间的影响。

4.3 数组越界与公式下标对齐

使用数组版写法时，常见问题是把nums[i-1]写成nums[i]，把range(2, n+1)写成range(1, n)。我自己的经验是：永远先统一“dp[i] 表示前 i 间”这个约定，再去对表。只要这个约定不乱，下标就乱不了。滚动变量版也有类似坑：更新顺序必须是从旧到新，如果写成prev1, prev2 = prev2, ...就会把新值覆盖进旧值。每次循环结束时的prev2, prev1 = prev1, cur是标准的交换更新，少写一行都会出错。

4.4 金额非负但这个细节值得多说一句

原题保证金额非负，所以dp[i]不会出现负数干扰。但如果碰到改编题把金额改成可正可负（比如带惩罚成本），就需要在转移时考虑“要不要主动放弃某些房子”。我处理这类问题时常用的技巧是：把dp初始化为极小值，并在不偷分支里保留0作为一个选项，相当于允许空手而归。这个点面试中偶尔会被追问，提前知道能省不少时间。

5. 变种串联：打家劫舍系全家桶一次吃透

5.1 环形数组变种：首尾相邻怎么办

Hot 100 体系里紧接着的一道变种是“房子围成一圈”，也就是 213 题。首尾相邻意味着第 0 间和第 n-1 间不能同时偷。常规解法是把问题拆成两个“线性打家劫舍”：一个区间是nums[0:n-1]（排除最后一间），另一个是nums[1:n]（排除第一间），取两者的最大值。

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

这里有个很容易被坑的地方：单元素数组必须单独返回nums[0]，不能直接跑两个rob_linear，因为nums[:-1]和nums[1:]都可能是空数组，导致结果全变 0。我第一次写这道变种时就因为这个特判没加，提交直接挂了一个用例。

5.2 二叉树上的打家劫舍：树形 DP 入门

再往后延伸就是 337 题，房子变成一棵二叉树的节点，直接相连的父子节点不能同时偷。这题的思路从“线性递推”变成“树上递归”。核心是每个节点返回两个值：偷本节点时子树的最大收益，以及不偷本节点时子树的最大收益。自底向上递归：

def rob(root): def dfs(node): if not node: return (0, 0) left_yes, left_no = dfs(node.left) right_yes, right_no = dfs(node.right) # 偷当前节点：左右孩子都不能偷 cur_yes = node.val + left_no + right_no # 不偷当前节点：左右孩子各自取较优 cur_no = max(left_yes, left_no) + max(right_yes, right_no) return (cur_yes, cur_no) yes, no = dfs(root) return max(yes, no)

这个版本把 DP 的状态定义和树的遍历结合在了一起，是树形 DP 的教科书案例。如果你能把线性版本理解透，树形版本只是把“相邻”换成了“父子”，转移逻辑仍然建立在“偷 / 不偷”两个状态上。我刷这道题时最大的感悟是：状态定义一旦选好，结构再复杂的题目也会变得有章可循。

5.3 删点成财：值域映射后的打家劫舍

还有一个常见变种是 740 题“删并获得点数”。题目给一个数组，每次选择某个值x获得x分，但必须删除所有值为x-1和x+1的元素。这个约束翻译一下就是：选了数字x就不能选x-1和x+1，相当于在“数值轴”上做相邻不可选。先把每个值的总和累加成sums[x]，然后对sums数组直接跑打家劫舍：

def delete_and_earn(nums): if not nums: return 0 max_val = max(nums) sums = [0] * (max_val + 1) for x in nums: sums[x] += x prev2, prev1 = 0, 0 for v in sums: cur = max(prev1, prev2 + v) prev2, prev1 = prev1, cur return prev1

这道题的难点不在于 DP 本身，而在于你能不能看出它与打家劫舍的同构关系。面试官从这里能考察“抽象建模”能力，而这恰恰是 Hot 100 刷题最值得训练的素养。

6. 从题目到体系：状态机视角与工程类比

6.1 状态机 DP：打家劫舍是极简原型

把打家劫舍的转移画成状态图，就是典型的两状态自动机：每个位置要么处于“偷”状态，要么处于“不偷”状态。偷状态的下一个位置必须是不偷，不偷状态的下一个位置可以是偷或不偷。这与股票买卖系列题目的“持有/不持有”状态机非常相似，只是股票问题多了“卖出价格、交易次数”等维度。理解打家劫舍的状态机，再去刷股票类题目会轻松很多。我后来做 LeetCode 上的股票系列时，经常回过来对比打家劫舍的状态设计，发现核心全都是：“维护一个到当前位置为止、以某种状态结束的最优收益。”

6.2 工程场景里的相邻约束

这类“相邻冲突”模型在现实中的投影也比比皆是：会议室预订时不能同时预订时间段重叠的房间、机房相邻机柜不能同时执行高耗电任务、直播推流时不能同时使用相邻网络通道的带宽。这些场景抽象出来都是“在一组对象中做选择，且相邻对象存在互斥约束，求最大总价值”。把打家劫舍理解成一个通用模型，比单纯记住一道题的解法有价值得多。

7. 刷题建议与面试表达技巧

7.1 面试时推荐的三步讲法

如果这道题出现在面试里，我建议按“暴力递归 -> 记忆化/动态规划 -> 滚动变量优化”三步来讲。先写暴力，展示你能建模；再说重复子问题，展示你能识别优化点；最后写滚动变量，展示空间意识。三步走完，面试官通常不会再刁难复杂度问题，反而可能会追问“如果输出具体偷哪些房子怎么改”。这个追问的解法是在 DP 数组之外再加一个choice数组记录每一步是否偷了当前房子，最后从后往前回溯。思路不难，但如果你没提前准备过，现场容易慌。

7.2 自查清单

我用这道题自测时，会把复杂度、边界、变种全部过一遍：

• 空数组、单元素数组是否直接返回正确值？
• 递推公式里dp[i-1]和dp[i-2] + nums[i-1]是否都能被正确解释？
• 滚动变量更新顺序是否先旧后新？
• 环形变种是否单独处理了n == 1？
• 能否在 5 分钟内切换到记忆化搜索版本？
• 能否一句话说明与股票买卖状态机的异同？

8. 一点个人的刷题心得

这道题我前后刷了至少五遍，每一遍都有新收获。第一遍只会套数组版模板；第二遍开始理解“前 i 间”状态定义的精妙；第三遍刷完环形和树形变种后，才真正建立起“同一模型在不同结构上迁移”的感觉；第四遍做股票系列时，才发现状态机视角原来早就藏在这道基础题里。我建议你也别只满足于“提交通过”，多问自己几个为什么：为什么不能贪心？为什么dp[i]只依赖前两个状态？如果改成环、改成树、改成二维网格，转移会怎么变？想清楚这几层，Hot 100 动态规划部分的整体框架也会跟着清晰起来。