企业官网建设流程全解析

198. 打家劫舍，一道题吃透动态规划的核心套路

刷过LeetCode的朋友对这道题都不会陌生，它就是动态规划入门序列里那道最经典的"198. 打家劫舍"。很多刚接触算法的同学一看题目描述，觉得这不就是一个隔一个拿钱的问题吗？结果上手一做，要么边界条件搞错，要么状态转移方程写反，要么被"数组越界"和"初始值设置"折腾到怀疑人生。

这道题的价值不在于题目本身有多难，而在于它把动态规划最核心的几个要素——状态定义、状态转移、边界初始化——以最干净的方式呈现了出来。你把它吃透了，后面的打家劫舍II（环形数组）、打家劫舍III（二叉树）、甚至股票买卖系列、背包问题，理解起来都会顺畅很多。这篇文章不打算只讲答案，而是把从"暴力递归"到"动态规划"再到"空间优化"的完整推导过程走一遍，把每一步为什么这么想、边界为什么这么设置，都用大白话讲清楚。

不管你是刚开始刷题的新手，还是刷了百八十道但DP还是似懂非懂的同学，这篇都值得认真看一看。我等下还会把环形版本（打家劫舍II）和树形版本（打家劫舍III）的解题思路也一并梳理，帮你把整个"打家劫舍"题目序列一次性打通。

1. 问题的本质：不是"隔一个偷一个"，而是"每一步做最优决策"

先看一眼原题描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

很多新手看完后的第一反应是：那不就是奇数下标和偶数下标分别求和，取大的那个吗？这个理解在部分用例下碰巧是对的，但并不可靠。比如[2, 1, 1, 2]，奇数下标和是1 + 2 = 3，偶数下标和是2 + 1 = 3，看起来都是3。但真正的答案是4，也就是偷第0间和第3间（2 + 2 = 4），中间虽然隔了两个房间，但只要不相邻就可以。这说明"隔一个偷一个"的直觉理解是错的，正确模型是"在不相邻约束下，选或不选的组合最优化"。

1.1 把选择权交给每一步：两个决策的反复权衡

我们可以换一个视角来理解这个问题。当你站在第 i 间房屋面前，你其实只有两个选择：

• 偷第 i 间，那么第 i-1 间就不能偷，你能拿到的最大金额是"前 i-2 间房屋的最大偷窃金额 + 第 i 间的金额"。
• 不偷第 i 间，那么第 i-1 间可以正常决策，你能拿到的最大金额就是"前 i-1 间房屋的最大偷窃金额"。

这两个选择，取金额更大的那个，就是前 i 间房屋能偷到的最高金额。注意这里的关键：我们不需要关心具体的偷窃方案是什么，只需要关心每个前缀范围上的"最优值"。这就是动态规划里典型的"无后效性"——第 i 步的决策只依赖前面已算出的最优子结构，而不依赖前面的具体决策路径。

1.2 为什么暴力递归会超时：重复计算的死循环

如果一开始没想到动态规划，最自然的想法是写递归。定义一个函数dfs(i)表示"从第 i 间房屋开始能偷到的最大金额"，那么递推关系是：

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

这个写法逻辑上完全正确，但实际跑 LeetCode 的用例，当数组长度到二三十以上时就开始明显卡顿，到四十以上基本超时。原因在于dfs(i)会被反复调用，比如计算dfs(4)需要dfs(3)和dfs(2)，计算dfs(3)又需要dfs(2)和dfs(1)，dfs(2)被算了两次，越往上层重复越多，整体是指数级的时间复杂度。

这里就引出了动态规划的核心动机：很多递归问题是"自顶向下"的思考方式，但大量子问题被重复求解。如果我们用数组把每个子问题的答案存下来，从最小的子问题开始"自底向上"地递推，就能避免重复计算，把时间从指数级降到线性级。

2. 状态定义与转移方程：DP 的灵魂在于"定义清楚一个状态"

动态规划的第一步永远是定义状态，这步走偏了，后面全是白搭。对于打家劫舍，最自然的定义是：

dp[i]表示"从前 i 间房屋（即下标 0 到 i-1）中能偷到的最大金额"。

注意这里用的是"前 i 间"，而不是"第 i 间"。这个定义的巧妙之处在于它把下标和"已经处理了几间房"对齐了：dp[0]表示一间房都没处理，自然是0；dp[1]表示只考虑第0间房，最大金额就是nums[0]。这种定义方式在写代码时边界非常干净，不需要额外的特判。

当然也有人习惯用dp[i]表示"前 i+1 间（下标0到i）能偷到的最大金额"，两种都可以，但后一种在初始化时要做dp[0] = nums[0]、dp[1] = max(nums[0], nums[1])之类的处理，边界相对麻烦一些。我自己更推荐"前 i 间"的定义，尤其是涉及到环形版本时，这个定义能省去很多头疼的边界判断。

2.1 状态转移方程：选择与不选择的数学表达

基于dp[i] = 前 i 间房屋的最优值，状态转移方程如下：

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

解释一下：dp[i-1]对应"不偷第 i-1 间房"（下标 i-1 是第 i 间）时的最优值；dp[i-2] + nums[i-1]对应"偷第 i-1 间房"所得，因为偷了它，前一间 i-2 就不能偷，所以只能累加dp[i-2]再加上当前房屋的金额。

这个方程看起来简单，但里面有一个新手特别容易犯迷糊的点：为什么dp[i-1]就一定代表"不偷第 i-1 间房"呢？它难道不是"前 i-1 间房的最优值"吗？万一dp[i-1]对应方案里刚好偷了第 i-2 间房，那和"偷第 i-1 间房"不就冲突了吗？

实际上不冲突。因为dp[i-1]的定义就是"前 i-1 间房能偷到的最大金额"，这个最大值方案中无论是否包含第 i-2 间房，都不影响我们把它作为"不偷第 i-1 间房"的候选值。因为既然不偷第 i-1 间房，那第 i-1 间房对我们没有任何约束作用，前 i-1 间房爱怎么偷怎么偷，取最优即可。而"偷第 i-1 间房"时，第 i-2 间房才被强制不能偷，这时用的是dp[i-2]。两个候选值分别对应两种互斥的决策，取 max 就是全局最优。这个逻辑想通了，动态规划算是入了门。

2.2 边界条件与初始化：出错率最高的环节

边界条件的设置是 DP 题最容易翻车的地方，打家劫舍也不例外。按照"前 i 间"的定义：

• dp[0] = 0：一间房都不偷，金额为0。
• dp[1] = nums[0]：只面对第0间房，偷它就是最大值，不可能是负数（因为金额非负）。

然后是遍历顺序：从i = 2开始，一直遍历到i = n（n 是房屋数量）。每一步都用dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])递推。最终答案就是dp[n]。

这里有个很多初学者踩过的坑：如果数组只有一个元素，dp[1]是没问题的，但如果直接申请dp数组长度为n然后试图访问dp[1]，就会越界。所以要么把 dp 数组开成n+1长度，要么在 n == 1 时提前返回。我自己写的时候习惯统一开n+1，并且让nums[i-1]的索引方式保持一致，这样即使 n=0 或 n=1 也不会出问题。

3. 完整实操：从递归到 DP 再到空间优化的三步演进

这部分是全文的重点，我会用 Python 和 C++ 两种语言分别演示，因为 LeetCode 上这两种语言的使用者最多。代码不是目的，理解每一步为什么这么写才是核心。

3.1 步骤一：记忆化递归（自顶向下）

先写出最朴素的递归，然后加一个memo字典或数组做记忆化。这是从暴力到 DP 的"缓坡"，也是很多教材推荐的入门路径。

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

这里的memo[i]表示"以下标 i 结尾的前缀能偷到的最大金额"，递归函数dfs(i)的语义和它一致。用-1初始化是因为金额非负，-1是一个合法的"未计算"标记。如果金额可以出现负数，那就要改用None或额外的visited数组。

记忆化递归的时间复杂度已经是 O(n)，空间复杂度 O(n)。它和迭代 DP 在本质上是同一套状态转移逻辑，只是思考方向不同。我个人在实际刷题中，如果第一时间想不出迭代怎么写，会先写记忆化递归保底，然后观察递归方向，再改写成迭代，这样思路不容易乱。

3.2 步骤二：迭代动态规划（自底向上）

这是最标准的写法，直接用一个dp数组，从前往后递推：

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

这段代码可以AC，但有几个细节值得抠一抠。首先dp数组长度是n+1，下标含义是"已处理的房间数"，dp[i]对应的是前 i 间房。其次，遍历时nums[i-1]是当前要决策的房间金额，dp[i-2]和dp[i-1]都是之前已经算好的值。最后返回值是dp[n]，不要写成dp[n-1]，这是很常见的粗心错误。

我在本地测试了几组数据验证正确性：

这里[2, 7, 9, 3, 1]是题目的标准示例，答案12对应2 + 9 + 1，注意它跳过了7和3，说明最优解不是固定间隔，而是动态决策出来的。

3.3 步骤三：滚动变量的空间优化

仔细看状态转移方程，dp[i]只依赖dp[i-1]和dp[i-2]，更早的状态完全没有用处。这意味着我们并不需要维护整个dp数组，只需要两个变量：

class Solution: def rob(self, nums: List[int]) -> int: 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分别表示"前 i-2 间"和"前 i-1 间"的最优值。每处理一个数num（代表当前房屋金额），新的最优值cur要么延续之前的最优（不偷当前房），要么是prev2 + num（偷当前房）。更新后，旧的prev1变成新的prev2，cur变成新的prev1，继续下一轮循环。

这个写法从一开始就解决了空数组和单元素的情况：nums 为空时循环不执行，直接返回prev1 = 0；nums 只有一个元素时，循环执行一次，cur = max(0, 0 + num) = num，返回num。非常干净。空间复杂度降为 O(1)，时间复杂度仍为 O(n)。

这里多啰嗦一句：滚动变量的优化不是打家劫舍独有的技巧，它是 DP 空间优化最常见的套路。当状态转移方程里第 i 步只依赖前面 k 步时，就可以只用 k+1 个变量轮转。后边的打家劫舍II（环形）也会用到同样的思想。

3.4 C++ 参考写法

考虑到不少读者用 C++ 刷题，这里也给出对应代码。C++ 里要注意vector的长度和索引，以及类型为int时可能发生的溢出问题（本题金额在 int 范围内，不需要额外的 long long，但稳妥起见可以用 long long 作为中间量的讨论我在后文会提到）。

class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; vector<int> dp(n + 1, 0); dp[1] = nums[0]; for (int i = 2; i <= n; ++i) { dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]); } return dp[n]; } };

用滚动变量优化后的C++版本：

class Solution { public: int rob(vector<int>& nums) { int prev2 = 0, prev1 = 0; for (int num : nums) { int cur = max(prev1, prev2 + num); prev2 = prev1; prev1 = cur; } return prev1; } };

两份代码跑同样的用例结果一致。从代码简洁度和可读性来看，滚动变量版本明显更优雅，面试时如果先写出数组版，再主动提到"其实可以滚动优化到 O(1) 空间"，通常是一个加分项。

4. 打家劫舍II（环形数组）的应对思路

原题是线性数组，题目的进阶版（打家劫舍II）把所有房屋首尾相连，变成一个环形。最后一家和第一家相邻，也就是说你不能同时偷第一间和最后一间。

这个变体刚出现时，很多人的第一反应是"把环形数组复制一遍接在后面"，其实这是个误区，接在后面会让相邻关系变得极其复杂。正确的思路是把问题拆掉：因为第一间和最后一间不能同时选，那么答案就是下面两个线性子问题的最大值：

• 不偷第一间：只考虑下标[1, n-1]的房屋，套用线性解法。
• 不偷最后一间：只考虑下标[0, n-2]的房屋，套用线性解法。

class Solution: def rob(self, nums: List[int]) -> int: n = len(nums) if n == 1: return nums[0] def rob_linear(arr): prev2, prev1 = 0, 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]))

注意这里有个小细节：当 n == 1 时，既不能切nums[1:]（会变成空）也不能切nums[:-1]（也会变成空），必须直接返回nums[0]。当 n == 2 时，nums[1:]和nums[:-1]各自只有一个元素，分别返回两个值，max 后就是正确结果，不会出问题。

这个"环形拆成两个线性区间"的思路非常经典，后面很多环形数组的 DP 问题都可以照搬。面试时如果能先讲清楚为什么要拆成两个区间，而不是生硬地套模板，会显得对问题有更深的理解。

5. 打家劫舍III（树形结构）的思路延伸

如果打家劫舍II还不够，还有第三版：房屋不是沿街排列，而是构成一棵二叉树的结构。两个直接相连的房子不能在同一晚被偷。这题和线性版本不同，不能直接用一维数组递推，需要做树形动态规划。

树形 DP 的核心思想是在树的每个节点上维护两个状态：

• f(node)：选择偷当前节点时，这棵子树能偷到的最大金额，等于node.val + g(left) + g(right)。
• g(node)：不偷当前节点时，这棵子树能偷到的最大金额，等于max(f(left), g(left)) + max(f(right), g(right))。

用后序遍历从叶子向上计算，每个节点只需要知道左右孩子的两个状态值。最终答案就是根节点的max(f(root), g(root))。

我对第三版的理解是：它把 DP 和树的遍历结合在了一起，也是对"状态定义"能力的又一次锤炼。如果你能把198. 打家劫舍的线性状态转移理解到位，再看树形版本就不会觉得是全新的东西，本质上都是在"相邻节点不能同时选"的约束下做最优决策，只是数据结构从数组换成了树。文章的重点是原题，但把三题的关联逻辑串起来，能帮你在面试中展示出系统性的知识框架。

6. 常见问题与排查技巧实录

这一节是我在实际刷题、以及帮别人 review 代码时见到的最高频问题整理。每一条都是真实踩过的坑，值得收藏。

6.1 dp 数组索引与房屋下标混淆

很多人第一次写数组版时，把dp[i]定义为"第 i 间房（下标 i）能偷到的最大金额"，然后初始化dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。这样也能做对，但遍历时容易混乱，比如nums[2]和dp[2]的关系要想半天。我推荐的"前 i 间"定义，可以让dp[i]和nums[i-1]的对应关系一目了然：dp 的下标表示"处理了几间房"，nums 的下标表示"第几间房"，二者天然错开1位，反而不容易混。

6.2 滚动变量更新顺序写反

滚动变量版最经典的错误是先更新prev2再更新prev1，导致prev1被覆盖成新值，下一轮计算用了错误的数据。正确顺序一定是先算cur，再把prev1赋值给prev2，最后把cur赋值给prev1。这个顺序本质上对应着"先读旧值，再写新值"，写代码时记住"旧值备份、递推、滚动"三步走。

6.3 对单个元素和空数组的处理不统一

代码在nums为空或只有一个元素时，很容易越界。用滚动变量版本天然规避了这个问题，因为循环天然不会执行或只执行一次，不需要额外特判。如果用数组版，最好在一开始就加上if n == 0: return 0和if n == 1: return nums[0]两个分支。我见过有的代码只处理了n == 0，没处理n == 1，然后 dp[1] = nums[0] 直接越界报错，这类低级失误完全可以靠统一边界分支来避免。

6.4 状态转移方程中"是否偷当前房"写反

有些同学会把方程写成dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])，看起来和正确写法只是顺序不同，逻辑一样。但有人会写错成max(dp[i-1] + nums[i-1], dp[i-2])，这就是把"相邻不能同偷"的条件给颠倒了。偷当前房时，必须把间隔拉开用dp[i-2]；不偷当前房直接沿用dp[i-1]。这个逻辑我建议在纸上画一个三列的小表格（i-2、i-1、i），写上下标对应的含义，就非常清楚。

6.5 测试用例设计的经验

刷这种题，不能只拿示例跑一遍就提交。我常用的自测用例包括：全为0的数组（结果应为0，检查是否被初始值-1干扰）、单调递增数组（结果应累加每隔一个的和）、单调递减数组（同上）、只有两三个元素的短数组（检查边界分支）、元素值很大的数组（确认没有溢出）。把这些用例跑通，再提交才比较稳。

6.6 关于整型溢出的提醒

LeetCode 原题的金额约束是0 <= nums[i] <= 400，数组最大长度通常到几百或上千，算出的最大值稳稳落在 int 范围内，不需要用 long long。但有些扩展题或面试官的追问会调大数值范围，如果金额上限调高，最优值可能超过2^31 - 1。这时用long long存是最稳妥的。C++ 里int和long long的混用很容易出隐性 bug，建议在一开始就统一类型。Python 没有这个问题，任意精度整数怎么算都不会溢出。

7. 这道题背后的思维模型：所有"选或不选"问题的通用框架

打家劫舍看起来是个小偷题材的趣味题，剥掉外壳之后，它其实是"序列决策"类问题的标准模板。类似的还有"粉刷房子"（每栋房子选不同颜色且不能相邻同色）、"按摩师预约"（不能接受相邻预约）、"最长递增子序列"（本质上也是每一步选或不选，只是约束更复杂）。处理这类问题，我的经验是四步走：

1. 寻找一组互斥的决策：在打家劫舍里，每个房屋面对"偷/不偷"；在更复杂的题里，可能是"选A/选B/选C"。
2. 定义状态表示"处理到当前范围时，各决策分别的最优值"：这里的状态可以是一个数，也可以是一个数组或多个变量。
3. 写出状态转移关系：当前状态如何由更早的状态计算而来，这一步是核心，也是最需要数学推导的。
4. 确认初始状态和边界条件：往往是最小的几个状态值，以及越界时的返回值。

把这四步走熟了，即使遇到没见过的题，也能先搭出框架再去填细节，而不是盯着题目发愁。我见过很多同学背了一堆模板题，遇到新题型就卡壳，症结就在于只记了代码，没有消化"状态定义"和"转移关系"这两层思维逻辑。打家劫舍之所以被当作 DP 入门的首选，正是因为它把这四步以最简单、最直观的方式完整呈现了一遍。

最后再分享一个我实战中的小习惯：拿到任何 DP 题，先别急着写代码，先口述一遍状态定义和转移方程，能流畅说清楚再动手。说的时候注意用词准确，"dp[i] 表示前 i 间房的最优金额，等于不偷第 i 间房的 dp[i-1]，或偷第 i 间房的 dp[i-2] 加当前金额，取其中较大者"。如果这句话能不打磕绊地说完，代码几乎是水到渠成。反过来，如果你发现自己说不清楚，那大概率是某个环节（通常是状态定义）还没想透，这时候写代码只会越写越乱。所谓"想不清楚就写不明白"，在动态规划这道题上体现得淋漓尽致。