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 和 3100 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 1dp[0] 代表“前 0 间”的最优值 0dp[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 0prev2 0。 处理 num 2cur max(0, 0 2) 2prev2 0prev1 2。 处理 num 7cur max(2, 0 7) 7prev2 2prev1 7。 处理 num 9cur max(7, 2 9) 11prev2 7prev1 11。 处理 num 3cur max(11, 7 3) 11prev2 11prev1 11。 处理 num 1cur max(11, 11 1) 12prev2 11prev1 12。最终 prev1 12和正确答案一致。3.3 手算验证拿样例跑一遍完整流程为了让你彻底放心再给你一个更复杂的例子走一遍。nums [2, 1, 1, 2]。基础版流程 dp[0] 0dp[1] 2dp[2] max(2, 0 1) 2dp[3] max(2, 2 1) 3dp[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] 1dp[2] max(1, 0 1) 1dp[3] max(1, 1 1) 2dp[4] max(2, 1 1) 2dp[5] max(2, 2 1) 3。结果也是 3符合预期。如果你手跑单一例子还是容易出错建议写一个包含 0 的用例比如 [0, 0, 0]。有 0 的房子意味着偷了也不增加收益但不增加收益的偷取依然会占据相邻位置因此 dp 会正确选择跳过它们。dp[1] 0dp[2] max(0, 0 0) 0dp[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 打家劫舍数组相邻不能偷dp[i] max(dp[i-1], dp[i-2] nums[i-1])213 打家劫舍 II环形数组首尾相邻拆成两个线性区间分别做 198337 打家劫舍 III二叉树父子不能同时偷后序遍历每个节点返回偷/不偷两个值看这张表你会发现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] 0dp[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 个项目每个项目有收益但不能连续两个季度做同一类项目求最大收益。你会发现数学模型一模一样只是换了皮。当你遇到这个场景时会想起这个“偷邻居”的模型这就是刷题的意义。