打家劫舍动态规划详解：LeetCode 198最大不相邻子序列

1. 题目到底在问什么：读懂“不相邻”三个字

先说结论：LeetCode Hot 100 里的第 198 题“打家劫舍”，是动态规划入门最经典的一道题。它表面上是一个入室盗窃的情景题，剥掉故事外壳之后，本质是一个“在数组中选数字，不能选相邻两个，求最大和”的最优化问题。这道题适合所有刚开始刷 hot100 题单的人，也适合准备面试、想系统掌握动态规划套路的技术人。

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

题目最核心的约束就是“相邻不能同时偷”。很多人第一次看这道题的时候，第一反应是——那我隔一间偷一间不就行了？比如数组 [2, 1, 1, 2]，隔一间偷是 2 + 1 = 3，但最优解其实是偷第 1 间和第 4 间：2 + 2 = 4。所以这个题的决策并不是简单的“隔一个偷一个”，而是要在每一个位置上都做一次选择：偷或者不偷，而且这个选择还会限制你后面的选择。

这就是必须用动态规划的第一个信号。为什么？因为你在第 i 间房子做决定时，会直接影响第 i + 1 间房子能不能偷。一个决策影响后面的决策，并且整个问题可以拆成“处理完前 i 间房子最多能偷多少”这种子问题，那就是典型的 DP 场景。相反，如果每个决策之间完全独立，直接贪心或者排序就能解决。这里的依赖性决定了必须用 DP。

还有一个容易踩的坑：有人会觉得这是“跳棋问题”，想用奇偶下标分组来解。这种思路在两个数间隔偷的时候是成立的，但一旦出现连续两间都很值钱的情况，比如 [3, 1, 1, 3]，下标分组是 3 + 1 = 4 和 1 + 3 = 4，碰巧对了。但换成 [5, 1, 1, 5] 分组也是 6 和 6，再看 [5, 3, 4, 5]，分组是 9 和 8，最优其实是偷第 1 间和第 4 间：5 + 5 = 10，而不是分组 9。所以下标分组法是错解，别用，后面会详细说为什么 DP 才是稳定的解法。

先想清楚暴力法，才能理解 DP 的价值。每间房子有偷和不偷两种选择，把所有可能性枚举一遍就是 2 的 n 次方种方案，n 只要到 50 就已经是天文数字，根本无法承受。而 DP 的核心思维就是把这个指数级的问题压缩成线性级：我不需要知道每一种具体方案长什么样，只需要保留“到当前位置为止，最优能偷多少”这个核心信息。这个压缩过程，就是状态定义的诞生过程。

这道题对新手最大的价值在于：它状态定义直白、转移方程逻辑清晰、代码不超过十行，但背后包含的动态规划思维方式和空间优化技巧，是几乎所有 DP 题目的通用底层逻辑。把这道题吃透，后面再做打家劫舍 II、III、股票买卖系列、背包问题，都会顺很多。

1.1 先别急着写代码：把生活场景翻译成数学问题

做算法题的第一步，不是打开编辑器写代码，而是先把题目的情景语言翻译成一个纯粹的数学问题。翻译得越准确，后面写代码就越不容易被多余信息干扰。

“打家劫舍”翻译出来是这样一句话：给定一个长度为 n 的非负整数数组 nums，我们需要找到一个子序列，这个子序列中不能包含原数组中相邻的两个元素，目标是让这个子序列的所有元素之和最大。

之所以强调“子序列”，是因为我们不需要真的偷连续的房子，跳着偷完全合法，只要不偷相邻的两间就行。换句话说，这个问题的数学模型是“最大不相邻子序列和”，英文里常叫 Maximum Sum of Non-Adjacent Elements。

这个数学模型才是题目的灵魂。面试的时候你把这段话讲给面试官，面试官立刻就知道你抓到了重点，而不是在背题。

子序列可以任意长，但不能包含相邻原下标。比如 [2, 7, 9, 3, 1]，你可以选 [2, 9, 1]（下标 0、2、4）得到 12，也可以选 [7, 3]（下标 1、3）得到 10，最优是 12。

翻译完数学模型，下一步是观察这个模型的“最优子结构”。什么叫最优子结构？就是说，整个问题的最优解，可以由子问题的最优解组合出来。

拿这道题来举例，如果我已经知道“从前 4 间房子里最多能偷多少”，要推导“从前 5 间房子里最多能偷多少”，我只需要关注第 5 间房子（也就是最后一个元素）偷不偷。如果偷，那第 4 间房子就不能偷，总量等于“从前 3 间房子的最优解 + 第 5 间的金额”；如果不偷，那总量等于“从前 4 间房子的最优解”。两种情况取最大值即可。

这就是最优子结构的直观体现：当前最优解，只依赖于前面已经算好的两个最优解，不需要回溯看更早的情况。这保证了我们可以从左到右扫描一遍就得到答案。

1.2 为什么第一反应应该是动态规划，而不是贪心

很多人刷题有个习惯：看到“求最大”就想贪心。贪心的意思是每一步都做当下最优的选择，希望局部最优能推出全局最优。这道题能不能贪心？不能。这里必须给出一个令人信服的例子，才能彻底说服自己。

看一个简单数组 [2, 3, 2, 4]。如果贪心，第一间房子 2 和 3 之间，3 更大，先偷第 2 间（金额 3）。偷完第 2 间，第 1 间和第 3 间都不能偷了，只能跳去偷第 4 间（金额 4），总共 3 + 4 = 7。但最优解是什么？偷第 1 间和第 3 间：2 + 2 = 4，不行。偷第 1 间和第 4 间：2 + 4 = 6，也不行。偷第 2 间和第 4 间：3 + 4 = 7，这就是贪心结果。看起来这里碰巧对了。

换个例子 [5, 1, 1, 5]。贪心会偷第一个 5，然后跳两个格子，跳到最后一个 5，总共 10。这个倒是最优解。但如果是 [5, 1, 2, 5] 呢？贪心偷第一个 5，跳到第三个元素 2，再跳到第五个元素——数组只有 4 个元素，所以没了，总共 7。其实最优是偷第一个 5 和最后一个 5，总共 10。贪心在第二步选了 2 而不是跳过它，结果少赚了 3。

问题的本质是：一个局部看起来很小的金额，可能会影响你能否拿到后面更大的金额。贪心的“短视”在这里会犯错，因为当前选择会限制未来选择的空间。这与经典的“最大子数组和”（LeetCode 53）不一样，那道题贪心是可以的，因为加一个负数大不了丢弃重新开始，不会永久失去后面的机会。而打家劫舍里，选了一个元素，直接废掉它旁边的元素，机会成本很高。

动态规划不同。DP 不急着在每一步做“当下最好”的选择，而是把每一种可能都算出来，然后保留最优的中间结果供后续使用。这就是为什么 DP 保证得到全局最优，而贪心不能。

如果这个例子还不够直观，你可以在纸上把 nums = [1, 2, 3, 1] 的情况写出来：最优是偷第 1 间和第 3 间，1 + 3 = 4。如果你第一步贪心选了 2，就只能 2 + 1 = 3，直接亏了 1。这就是贪心失败的铁证。

同时，我还要提一下另一种常见的错误思路：“隔一个偷一个”——也就是奇偶分组。有人觉得奇数下标的总和和偶数下标的总和，取一个大的就行。但这只在“每两间偷一间且位置固定”的假设下成立，而这个假设本身就不符合题意。看这个数组 [3, 1, 10, 1, 3]，奇数下标是 3 + 10 + 3 = 16，偶数下标是 1 + 1 = 2，分组法会选 16。实际最优确实是偷下标 0、2、4 的 3、10、3，碰巧 16。但换成 [3, 1, 10, 100, 3]，奇数下标 3 + 10 + 3 = 16，偶数下标 1 + 100 = 101，分组法选 101。但最优解是什么？偷下标 0、2、3？不行，2 和 3 相邻。偷下标 0、2、4 是 16，偷下标 1、3 是 101，最优就是 101——又碰巧对了。但 [3, 10, 1, 100, 3] 呢？奇数分组 3 + 1 + 3 = 7，偶数分组 10 + 100 = 110。最优是偷 10 和 100？下标 1 和 3 不相邻，110 确实可以。好像分组法总是对的？不对，看 [3, 1, 100, 1, 3]，奇数分组 3 + 100 + 3 = 106，偶数分组 1 + 1 = 2，最优是 106？偷 0、2、4 就是 106，没问题。但要小心分组法隐含了“同一组内全选”的假设，这是不成立的。比如 [2, 100, 2, 100, 2]，奇数分组 2 + 2 + 2 = 6，偶数分组 100 + 100 = 200。最优确实是 200（偷下标 1 和 3，不相邻）。再看 [100, 1, 1, 100, 1]，奇数 100 + 1 + 1 = 102，偶数 1 + 100 = 101，分组选 102。但真正最优是偷下标 0 和 3：100 + 100 = 200，因为中间下标 1 和 2 都不偷。这里分组法就彻底错了，因为它没有“跳过两个房间再偷”这个选项——它只允许固定每隔一间偷一次，而题目允许任意跳过多个房间。所以，再次强调，分组法是错的，只有 DP 能正确处理任意跳过的场景。

2. 状态定义与转移方程：从0开始手推

动态规划题目最关键的一步就是状态定义。状态定义对了，转移方程大概率也就顺理成章推出来了；状态定义错了，后面越写越别扭，甚至陷入思维死胡同。

这道题最标准的做法是定义一个一维数组 dp，其中 dp[i] 表示“从前 i 间房子中能偷到的最大金额”。注意这里的措辞：是“前 i 间”，不是“第 i 间”。这个区分非常重要。dp[i] 描述的是一个前缀范围内的最优结果，而不是“必须偷第 i 间”。这样定义的好处是，最终答案就是 dp[n]，不需要额外遍历找最大值。

那么问题来了：dp[i] 怎么由更小的子问题推导出来？我们要分情况讨论——这是动态规划的核心思考方式，叫作“考虑最后一步”。

当我们已经处理到第 i 间房子（也就是下标 i - 1 的房子，因为 dp 从 1 开始计数）时，摆在我们面前的无非是两个选择：

第一个选择：偷第 i 间房子。那第 i - 1 间房子绝对不能偷。此时的总金额等于“前 i - 2 间房子的最优解 + 第 i 间房子的金额”，也就是 dp[i - 2] + nums[i - 1]。

第二个选择：不偷第 i 间房子。那这个位置就不贡献任何金额，此时的总金额等于“前 i - 1 间房子的最优解”，也就是 dp[i - 1]。

我们要的最优解就是在“偷”和“不偷”之间取较大值，于是就有了这个经典的转移方程：

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

就这么简单。但这个方程里埋了很多初学者容易忽略的细节，下面一个一个小节拆开讲清楚。

2.1 dp[i] 到底是什么：前缀最优解，不是强迫偷第i间

先把 dp[i] 这个状态钉死。我见过很多人第一次写这道题时，把 dp[i] 理解成“偷到第 i 间房子时能获得的最大金额”，然后就写出了一个奇怪的转移：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])。其实这个写法在语义上是有歧义的——如果 dp[i] 表示“前 i 间”，那么最后一间就是 nums[i - 1]；如果 dp[i] 表示“到第 i 间为止”，那么末元素是 nums[i]。两种写法都能对，但混在一起就会出 bug。

推荐用“前 i 间”这个定义，因为它在语义上和最终答案 dp[n] 对齐，不用额外处理“到第 n - 1 个下标为止”这种别扭的表述。dp[i] 的含义是：考虑数组的前 i 个元素，在满足“不能偷相邻房子”约束下的最大金额。至于第 i 间偷不偷，dp[i] 本身不承诺，它只是把两种情况的最优值打包起来。

为了加深理解，可以看一个具体的小例子。nums = [5, 3, 4, 11, 2]，从左到右推：

dp[0] = 0，因为没有房子可偷。 dp[1] = 5，因为只有一间房子，不偷白不偷，偷它。 dp[2] = max(dp[1], dp[0] + nums[1]) = max(5, 0 + 3) = 5。这里“偷第2间”反而亏了，因为一旦偷了 3，就不能偷第一间的 5。所以 dp[2] 仍然保持 5。 dp[3] = max(dp[2], dp[1] + nums[2]) = max(5, 5 + 4) = 9。这里偷第 3 间，加上前面第一间的 5，总共 9，比不偷（5）好。 dp[4] = max(dp[3], dp[2] + nums[3]) = max(9, 5 + 11) = 16。偷第 4 间（11），加上 dp[2]（即前两间最优 5，对应偷第一间 5），总共 16。 dp[5] = max(dp[4], dp[3] + nums[4]) = max(16, 9 + 2) = 16。最后这间房子不值得偷，因为不偷已经能达到 16。

数组 [5, 3, 4, 11, 2] 的最优方案是偷第 1 间（5）和第 4 间（11），总金额 16。注意，dp[4] 取的是“dp[2] + 11”，说明那时的最优组合是 5 + 11，中间跳过了很多房子，这正是 DP 的灵活之处——它允许任意跳跃，只要不相邻即可。

2.2 转移方程的两条路，逐行拆开讲

转移方程 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]) 只有一行，但背后包含的逻辑值得掰开揉碎讲清楚。

先看 dp[i - 1] 这一项。它的意思是：第 i 间房子我们不偷，那么结果就完全继承前 i - 1 间房子的最优解。这是最直觉的一种情况——你走到了这间房子门口，想想算了，不进去，那你的收益和在前 i - 1 间房子时一模一样。关键词是“继承”。

再看 dp[i - 2] + nums[i - 1] 这一项。它的意思是：我们决定偷第 i 间房子，于是立刻得到 nums[i - 1] 的现金。但与此同时，第 i - 1 间房子变成禁区，不能偷了。所以前面只剩下前 i - 2 间房子的空间，最优解就是 dp[i - 2]。这两部分加起来，就是偷第 i 间的总收益。关键词是“跳过”。

很多人问：为什么不是 dp[i - 1] + nums[i - 1]？因为如果偷第 i 间，第 i - 1 间就废了，直接拿 dp[i - 1] 来加，就意味着把第 i - 1 间也偷了（或者至少考虑了它），这是矛盾的。所以必须跳过一层，回到 dp[i - 2]。

这个“跳到 i - 2”的思想，是打家劫舍整个系列的精髓。到了打家劫舍 II（环形房屋），你仍然需要靠这个思想去拆解问题；到了打家劫舍 III（二叉树），你把线性跳步变成了“子树选择”。可以这么说：理解不了跳过这一步，后面所有变形题都会卡壳。

再换个视角看这个方程：它本质上是一个带条件的累加过程。你可以把 dp 数组想象成一条流水线，每个位置都把它前面两个位置的“最优状态”拿过来，做一个二选一。这种形式在 DP 里极其常见——很多题的状态转移都长这样：要么用上一个位置的状态，要么跨一步用上上个位置的状态再加当前值。比如“打家劫舍”的兄弟题——爬楼梯（LeetCode 70），状态转移是 dp[i] = dp[i - 1] + dp[i - 2]，那是一条加法路径；而这里是一条 max 路径，逻辑非常相似，但决策语义完全不同。放在一起对比记忆，DP 就不再是一道题一个背法，而是成体系的套路。

2.3 边界和初始化：最容易翻车的地方

动态规划题里，边界条件是最容易被轻视、但也最容易在面试时翻车的地方。打家劫舍的边界条件一共有三个，必须全部想清楚再写代码。

第一个边界是 n = 0，也就是没有房子可偷。这种情况直接返回 0 就行。实际工程里可能是空数组、空列表，一定要提前判空，不然后面访问 nums[0] 直接报下标越界。

第二个边界是 n = 1，也就是只有一间房子。这时没有“相邻房子”的概念了，唯一的选择就是偷它，返回 nums[0]。有的代码会把 dp 数组长度为 n + 1，此时 dp[1] = nums[0]，只在循环里从 i = 2 开始，依然能正确运行；但如果 n 为 1，循环根本不进去，最后返回 dp[1] 就是 nums[0]。所以关键在于 dp[1] 的初始化。

第三个边界，也是最隐蔽的一个：dp[i - 2] 在下标 i = 1 的时候访问 dp[-1]，这是非法的。所以标准写法里，循环要从 i = 2 开始，i = 1 的情况单独初始化，或者把 dp 数组开长一格，用 dp[i] 表示“到第 i 个房子为止”并让 dp[0] = 0、dp[1] = nums[0]，再从 i = 2 开始循环。

这里分享一个我面试时常用的技巧：与其纠结各种下标错位，不如把 dp 数组长度设为 n + 1，dp[0] 代表“前 0 间”的最优值 0，dp[1] 代表“前 1 间”的最优值 nums[0]，然后写一个 for 循环从 i = 2 遍历到 n。这样下标含义统一，不易写错。

为了彻底杜绝下标混乱，我再给一个自查方法：在你写完代码后，用 nums = [1, 2, 3, 1] 这个标准样例手算一遍，把每一轮的 dp 值写出来，确认和代码的输出一致。比如：dp[0] = 0, dp[1] = 1, dp[2] = max(1, 0 + 2) = 2, dp[3] = max(2, 1 + 3) = 4, dp[4] = max(4, 2 + 1) = 4。答案 4，正确。如果手算发现在某一步出现了负数或者明显不合理的值，那大概率是下标用错了。

3. 代码落地与空间优化：从O(n)到O(1)

理论推导完，就该动手写代码了。我会先给一个最直白、最容易理解的基础版本，然后再做空间优化。很多新手一上来就追求最优解，反而把自己绕晕了。正确的学习路径是：先让代码正确，再让它高效。

3.1 基础版代码：先让逻辑跑通

最直白的做法就是开一个 dp 数组，长度 n + 1，按转移方程填满，最后返回 dp[n]。

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]

这段代码的优点是直观，每一步的 dp 值都留存在数组里，方便调试时打印查看。比如你想确认自己推导对不对，可以加一行 print(dp)。

时间复杂度是 O(n)，空间复杂度也是 O(n)。对于这道题来说，n 的范围通常不大，但面试官一定会追问：能不能把空间优化到 O(1)？

3.2 滚动变量优化：面试官最爱问的下一步

观察转移方程，你会发现 dp[i] 只依赖于 dp[i - 1] 和 dp[i - 2]，也就是说，在计算当前位置时，我们只需要知道前两个位置的值，更早的值完全没有作用。既然这样，我们完全可以用两个变量滚动维护，没必要把整个数组都保存下来。

具体做法是维护 prev2 表示 dp[i - 2]，prev1 表示 dp[i - 1]。每次计算出当前值 cur 之后，把 prev1 赋值给 prev2，把 cur 赋值给 prev1，相当于整体向右平移一格。

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

这是全场最优雅的写法之一。很多 LeetCode 讨论区置顶题解就是这个版本，建议直接记在心里。它的空间复杂度降到了 O(1)，时间依然是 O(n)。

一个必须注意的点是循环里的更新顺序：必须先 prev2 = prev1，再 prev1 = cur。如果写反了，把 prev1 先覆盖成 cur，那 prev2 就永远拿不到旧值了，结果会完全错误。这里我踩过坑，所以特别提醒一句：顺序错了不是结果差一点，而是直接错得离谱。

我们来手算一遍这个优化版：nums = [2, 7, 9, 3, 1]。

初始 prev1 = 0，prev2 = 0。 处理 num = 2：cur = max(0, 0 + 2) = 2，prev2 = 0，prev1 = 2。 处理 num = 7：cur = max(2, 0 + 7) = 7，prev2 = 2，prev1 = 7。 处理 num = 9：cur = max(7, 2 + 9) = 11，prev2 = 7，prev1 = 11。 处理 num = 3：cur = max(11, 7 + 3) = 11，prev2 = 11，prev1 = 11。 处理 num = 1：cur = max(11, 11 + 1) = 12，prev2 = 11，prev1 = 12。

最终 prev1 = 12，和正确答案一致。

3.3 手算验证：拿样例跑一遍完整流程

为了让你彻底放心，再给你一个更复杂的例子走一遍。nums = [2, 1, 1, 2]。

基础版流程： dp[0] = 0，dp[1] = 2，dp[2] = max(2, 0 + 1) = 2，dp[3] = max(2, 2 + 1) = 3，dp[4] = max(3, 2 + 2) = 4。

最优方案是偷第 1 间和第 4 间：2 + 2 = 4。发现没有，中间第 2 间和第 3 间都不偷，这是一种“连续跳过两间”的方案，而之前说的错误思路——奇偶分组法——是永远无法表达这种方案的。这里再次印证了 DP 的威力：状态压缩不代表丢失灵活性，dp[i - 2] 的跨一步，其实已经隐含了跳任意多步的可能，因为 dp[i - 2] 内部可能就涵盖了跳过好几间的方案。

再拿一个全是 1 的极端例子：nums = [1, 1, 1, 1, 1]，正确答案是隔一间偷一间，总共偷 3 间，总额 3。用递推跑一遍：dp[1] = 1，dp[2] = max(1, 0 + 1) = 1，dp[3] = max(1, 1 + 1) = 2，dp[4] = max(2, 1 + 1) = 2，dp[5] = max(2, 2 + 1) = 3。结果也是 3，符合预期。

如果你手跑单一例子还是容易出错，建议写一个包含 0 的用例，比如 [0, 0, 0]。有 0 的房子意味着偷了也不增加收益，但不增加收益的偷取依然会占据相邻位置，因此 dp 会正确选择跳过它们。dp[1] = 0，dp[2] = max(0, 0 + 0) = 0，dp[3] = max(0, 0 + 0) = 0。答案 0。这个例子看似无聊，但对理解“偷 0 金额没有意义”是有帮助的。

4. 往深了挖：从198到DP题型迁移

一道题刷完就扔，是最浪费的做法。刷 hot100 的正确姿势是横向对比、纵向延伸。第 198 题在 LeetCode 上其实是一个“打家劫舍”系列的开端，后面还有第 213 题（环形房屋）和第 337 题（二叉树房屋）。把这三题放在一起对比，你会发现它们用的是同一个底层模型，只是加了一些约束，需要你对状态定义做相应调整。

4.1 打家劫舍全家桶：环、树、其他变体

先看 213 题“打家劫舍 II”。区别在于房屋围成了一个环，第一间和最后一间也相邻。这时候不能直接套用 198 的解法，因为第一间和最后一间可能在同一个方案里被同时偷。解决办法非常巧妙：把环拆成两个线性问题。

方案一走一遍线性区间 nums[0:n-1]（不偷最后一间，确保第一间可以偷），方案二走一遍线性区间 nums[1:n]（不偷第一间，确保最后一间可以偷）。最后取两个方案的最大值即可。注意不要忘记处理 n = 1 的特殊情况，直接返回 nums[0]。

再看 337 题“打家劫舍 III”。房屋结构变成了一棵二叉树，父子节点不能同时偷。这题的 DP 状态变成了每个节点返回两个值：偷这个节点时，以它为根的子树能偷到多少；不偷这个节点时，又能偷到多少。后序遍历自底向上，每个节点根据子节点的两个值来决定自己偷不偷。这类 DP 叫树形 DP，是最常见的一类进阶题。

我之前整理过一个小表格，方便三种情况对比：

看这张表你会发现，198 题只是体系入口，真正的价值在于为 213、337 提供了思考基础。如果你把 198 搞透了，213 的拆环思路、337 的树形状态设计，理解起来都会轻松很多。

4.2 和它长得很像但解法不同的题

刷题过程中最怕的一种情况是：题目长得像，但解法其实完全不同，一旦思维定势就会掉坑。打家劫舍就特别喜欢和另外几道题混淆。

最容易混的是“最大子数组和”（LeetCode 53）。这两道题都是在数组上选元素求最大和，但 53 要求选出的元素必须连续相邻，而 198 要求不能相邻。解法也因此完全不同：53 用的是 dp[i] 表示以第 i 个元素结尾的最大子数组和，转移是 dp[i] = max(nums[i], dp[i - 1] + nums[i])，因为连续子数组要么从左边的连续段延续过来，要么从当前元素重新开始；198 用的则是 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])，因为不相邻选择可以直接跳过上一个元素。两者一个“必须连”，一个“必须断”，正好相反。

另一道容易混的是“爬楼梯”（LeetCode 70）。爬楼梯的状态转移是 dp[i] = dp[i - 1] + dp[i - 2]，是一个累加关系，因为到达第 i 级台阶的方法数等于从 i - 1 走一步加上从 i - 2 走两步。198 的转移是取 max 而不是相加，因为目标和约束都不一样。如果你发现自己在 198 里写出了加号，基本就是思路跑偏了。

还有“股票买卖 I”（LeetCode 121），也是数组求最大收益，但它本质是一个“只允许一次交易”的问题，核心是维护历史最低价，用动态记录的“当前价格减历史最低价”去更新答案就可以了。它的状态不需要考虑跳过相邻元素，因为它只买一次卖一次，约束完全不同。

把这几道题放在一起对比，能帮你建立一个认知：动态规划不是一个固定模板，而是根据约束条件灵活设计状态和转移。198 教你的，是“有互斥约束时怎么设计状态”，这个思维可以迁移到很多场景，而不仅仅是数组。

4.3 从这道题提炼出的通用DP套路

刷了 198 之后，我强烈建议你把它上升为方法论。动态规划题的通用解题步骤，可以归纳为六步。

第一步，划分子问题。想清楚大问题怎么切成小问题。在 198 里面，子问题就是“前 i 间房子”。

第二步，定义状态。用 dp[i] 或 dp[i][j] 准确描述子问题的解。这步最重要，如果状态定义不清楚，后面全白搭。在 198 里，状态是“前 i 间房子的最大偷窃金额”。

第三步，写转移方程。核心是“考虑最后一个元素/最后一次决策”。把当前的问题用前一个或前两个状态表示出来。在 198 里就是偷或不偷第 i 间的二选一。

第四步，初始化边界。把最容易出错的基础情况（空数组、单元素、首尾）处理好。

第五步，确定遍历顺序。通常是从左到右、从下到上，保证计算当前状态时，依赖的子状态已经算好。

第六步，空间优化。看转移方程的依赖范围，如果只依赖前两个状态，就用滚动变量压缩空间。

这套六步法，不仅适用于 198，也适用于后面几乎所有一维 DP 题。真正把这个流程内化之后，你再遇到新题就不会慌，而是按部就班走流程。

5. 面试现场与常见坑位盘点

这一章是实操经验的浓缩。很多人在 LeetCode 上能写出正确答案，一到面试就卡壳，区别往往不在代码能力，而在表达方式和对边界情况的处理。

5.1 在面试官面前怎么一步步讲出来

面试官让你做这道题，他真正想看的不是你有没有背过答案，而是你的思考轨迹。正确的打开方式是这样：

先说理解：“这道题就是一个一维数组上选数字求最大和的问题，约束是相邻两个数不能同时选。”

接着抛暴力解：“最朴素的做法是枚举所有子集，复杂度 2 的 n 次方，这肯定不行。”

再引入 DP：“我发现这个问题有一个最优子结构：我只需要知道前 i - 1 间的最优值和前 i - 2 间的最优值，就能推导前 i 间的最优值。因为面对第 i 间，我只有两个选择——偷或不偷，偷的话必须跳到 i - 2，不偷的话就是继承 i - 1。”

然后写出转移方程并解释：“所以 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])，前者是不偷第 i 间，后者是偷第 i 间，两种情况取最大值。”

最后补上边界和优化：“边界条件是 dp[0] = 0，dp[1] = nums[0]。另外因为只依赖前两个状态，我可以把空间压缩到 O(1)，用两个滚动变量。”

这一套说下来，面试官基本能确认你是真的理解，而不是背题。切记不要一上来就写最优解，那样反而可能让人觉得你只是刷题刷得多，而不一定理解背后的原理。

5.2 易错点自查清单

把我在实际刷题和辅导别人过程中遇到的常见错误整理成一份清单，建议写代码前瞄一遍。

第一，忘记判空。输入 nums 为空时会直接访问 nums[0]，报 IndexError。必须先处理 n == 0 的情况。

第二，下标混乱。dp 数组用“前 i 间”定义时，第 i 间的金额对应 nums[i - 1]，写代码时经常有人写成 nums[i]，导致越界或取值错误。

第三，初始化遗漏。dp[1] = nums[0] 忘了初始化，导致循环里 dp[i - 2] 和 dp[i - 1] 都是 0，结果全错。

第四，空间优化的更新顺序写反。必须先更新 prev2 = prev1，再更新 prev1 = cur，不能反过来。

第五，返回值取错。有人会写成 return dp[n - 1] 或者 return max(dp)。用“前 i 间”定义时，最终答案就是 dp[n]；用了滚动变量就是 prev1。DP 数组里未必是最后一个值最大吗？其实 dp 数组是单调不减的，因为“可以偷更多的房子”这个选项永远存在——至少可以选择不偷新房子，所以 dp[n] 一定是整个数组的最大值，不需要再取一次 max。

第六，忽略 n == 1 的情况。虽然用滚动变量写法可以自动处理，但如果用基础数组写法，n == 1 时要单独返回 nums[0]。

这份清单看起来简单，但每一条都是我本人或者周围同事真实犯过的错。面试时一个小错就可能影响整体评价，一定要在提交前逐条核对。

5.3 刷题之外的一个小建议

最后分享一个我的个人习惯，算是对这道题的一个延伸价值。我不会只满足于把这道题 AC，而是会做三件额外的事。

第一件，隔一段时间把代码遮住，重新手写一遍这道题。如果第二次写还能一次通过，说明真的理解了；如果写不出来，说明之前只是记忆，不是掌握。

第二件，把转移方程用自然语言讲给一个不懂算法的人听。如果你能用一个生活化的类比让对方明白“为什么偷第 i 间要跳到 i - 2，因为邻居家会报警”，那你自己才真正想透了。解释本身就是最好的学习方式。

第三件，尝试把这道题的思路套到一个新场景里。比如公司有 n 个项目，每个项目有收益但不能连续两个季度做同一类项目，求最大收益。你会发现，数学模型一模一样，只是换了皮。当你遇到这个场景时，会想起这个“偷邻居”的模型，这就是刷题的意义。