力扣 198 题 House Robber也就是“打家劫舍”在算法题圈子里几乎人人刷过。它被归为“动态规划”分类而且是最标准的一维动态规划模板。题目本身非常简单一排房子每间房里有金额不等的现金你不能偷相邻两间问一晚上最多能偷多少。但就是这么一道简单题我在面试候选人、也在我自己反复刷题的过程中发现很多人能背出答案却讲不清楚状态为什么这样定义、转移方程为什么是dp[i] max(dp[i-1], dp[i-2] nums[i])更不用说在 n1 或者空数组这种边界条件下翻车。所以这篇笔记不打算只贴一段能通过的代码而是把“一维动态规划”从暴力递归到记忆化搜索再到标准 DP 数组、滚动数组优化这条完整路径拆开讲透。不管你是刚开始刷 LeetCode 的初学者还是在准备面试想把这类型题说得更有条理这篇都值得耐心读完。写完之后你会发现House Robber 不仅仅是“力扣热题 100”里的一道简单题它几乎是一维 DP 所有重要概念的浓缩状态定义、转移方程、边界条件、空间压缩。把这题吃透后面再碰到零钱兑换、爬楼梯、跳跃游戏这类一维 DP 题思路会顺畅很多。1. 题目理解与解题思路为什么“隔一家偷一次”靠不住1.1 先读懂题目别急着写代码House Robber 的题目描述很直观你是一个专业小偷计划偷窃沿街的房屋。每间房内藏有一定现金影响你作案的关键约束是如果两间相邻的房屋在同一晚上被闯入会惊动安保系统。也就是说你不能偷相邻的两间房。给定一个非负整数数组nums其中nums[i]代表第 i 间房里的金额要求计算出不触发警报的前提下你今晚能偷到的最大金额。把它抽象成纯算法问题就是给定一个非负整数数组选出一个子序列要求子序列中任意两个元素在原始数组中不相邻求这个子序列的元素和最大值。举个人人都能看懂的示例。比如nums [1, 2, 3, 1]最优方案是偷第 1 间和第 3 间也就是 1 3 4。如果你偷第 2 间和第 4 间得到 2 1 3不如前者。再比如nums [2, 7, 9, 3, 1]最优方案是偷第 1、3、5 间即 2 9 1 12而不是简单地把奇数位全部加起来或者偶数位全部加起来就完事。为什么不是 7 3 10因为那只是“隔一家偷一次”的其中一种固定模式并不是最优。我经常和刷题的人说拿到这种题第一件事不是想“能不能贪心”而是先把问题用数学语言重新描述一遍。数组、子序列、求最值这三个关键词凑在一起动态规划就是非常自然的候选方案。这里最核心的操作是“选或不选”对于每一间房你只有两个选择偷它或者不偷它。一旦确定了这间房是否偷相邻房屋的可行性就受到了限制。这种“当前决策影响后续选择空间”的模型恰好是动态规划最擅长的场景之一。1.2 贪心思路为什么不行很多人第一次看到这道题会冒出一个直觉既然不能偷相邻的那我就隔一家偷一家或者我每次都偷当前能偷的最大金额。这两种直觉都是典型的贪心思路可惜都不成立。先说说“隔一家偷一家”的问题。它隐含假设了被偷的房子之间必须恰好空一个房间但题目只要求“不相邻”完全没有说不能隔两间、隔三间。看一个反例nums [2, 1, 1, 2]。按“隔一家偷一家”来算偷第 1、3 间得到 2 1 3但如果偷第 1、4 间得到 2 2 4这一步直接空了两间房结果反而更大。这说明最优解里被跳过的房屋数是不固定的不能用一个简单的固定间隔概括。再说说“每次取当前最大可偷金额”的策略。举个反例nums [3, 2, 3, 2, 3]。如果你第一间就选择了最大的 3那么第二间被锁死不能选之后你只能在第三间和第五间里再选比如偷第一间和第三间、或者第一间和第五间最多也就 6。但如果你放弃第一间转而偷第二间和第四间得到 2 2 4也不是最好。最优是偷第一间、第三间、第五间3 3 3 9。这里问题在于单看某一间很大不代表选了它之后整条路径最优因为它会封死旁边一间原本可能更优的选择。贪心失败的根本原因在于局部最优无法推出全局最优。当前房间中金额大的不一定是最终路径的一部分你可能为了一个比较大的值失去了右侧连续更优的组合。遇到这种“每个位置做选择选择之间有约束要求全局最值”的模型应该立刻想到动态规划而不是在贪心的死胡同里继续优化。1.3 动态规划为什么合适动态规划之所以适合本题是因为它天然具备两个关键性质。第一个是最优子结构。假设我们已经知道前 i-1 间房能偷到的最大金额是dp[i-1]前 i-2 间房能偷到的最大金额是dp[i-2]那么对于第 i 间房我们只需要在这个两个信息基础上再做一次比较就能得到前 i 间房的最优值。当前房间偷还是不偷这两个分支都已经可以被之前的子问题完整描述。第二个是无后效性。在状态转移时我们只关心“前 i 间房最多能偷多少”而不需要关心到底偷了哪几间、最后一间是不是偷了。因为题目只限制相邻关系已经偷过的房屋只会影响“下一间能不能偷”这一个事实而不会影响更久远的选择。把历史信息压缩成dp数组里的一个数值就是无后效性的直接体现。从这两个性质出发一维 DP 的骨架就出来了一个一维数组dp其中dp[i]表示前 i 间房或者说考虑下标从 0 到 i 的这些房屋能偷到的最大金额。有了这个定义接下来的问题就是怎么从dp[i-1]、dp[i-2]推出dp[i]也就是传说中的状态转移方程。这个过程像搭积木每一块都在前两块的基础上选择最优路径最后拼出全局答案。2. 状态设计与状态转移方程一维DP的关键细节2.1 状态定义怎么写最不容易错动态规划题最怕的不是转移方程写不出来而是状态定义一开始就写得含糊。House Robber 里最常见的状态定义有两种写法我分别说一下它们的区别和适用场景。第一种写法是dp[i]表示“考虑前 i 间房屋时能偷到的最大金额”下标从 1 开始对应第 1 间房。这种写法下dp[0]表示没有房屋时的最大金额自然为 0dp[1] nums[0]表示只有一间房时只能偷它。用这种方式定义时代码里的循环可以从 i1 一直扫描到 n边界处理相对统一非常推荐。第二种写法是dp[i]表示“从 0 到 i 这 i1 间房屋中以第 i 间房屋为结尾考虑时能得到的最大金额”也就是下标直接和原数组对齐。这种写法在代码里更常见但你必须单独处理 i0 和 i1 的初始化循环还得从 2 开始下标细节特别容易写错。我个人更推荐把下标错开一位的写法也就是让dp[i]对应“前 i 个房屋”其中dp[0]天然表示空集。这样有几个好处不需要对数组长度做特殊判断代码逻辑统一转移时dp[i-1]、dp[i-2]不会出现负下标问题后续如果扩展到打家劫舍 II、打家劫舍 III这种“多了一个空位”的定义方式也更方便处理环形和树形结构。很多一线工程师写 DP 题也倾向于这种偏移一位的写法就是因为它能把边界坑减少一大半。无论是哪种定义方式建议你在写代码前先在注释里写清楚一句话“dp[i]代表什么”。这一句话写清楚了后面的转移方程、初始化、返回值就都有了依据。很多人在刷题时省略这一步结果写着写着下标就乱了再回来改状态定义往往比重新写一遍还费时间。2.2 转移方程推导选与不选的二选一状态定义确定后转移方程其实是顺水推舟。我们站在第 i 间房屋面前面临两个选项。选项一不偷第 i 间房。那么第 i-1 间房偷不偷都无所谓结果直接等于前 i-1 间房的最优解也就是dp[i-1]。选项二偷第 i 间房。一旦偷了这一间第 i-1 间房绝对不能偷所以我们能用的最优方案来自前 i-2 间房再加上当前这间的金额nums[i-1]因为下标偏移了一位第 i 间房对应nums[i-1]也就是dp[i-2] nums[i-1]。综合起来转移方程就是dp[i] max(dp[i-1], dp[i-2] nums[i-1])这里有个初学者最容易犯错的地方就是为什么偷第 i 间时用的是dp[i-2]而不是dp[i-1]。原因是你不能偷相邻的两间房。如果偷了第 i 间那么第 i-1 间就一定不能偷所以前面能沿用的最优解必须是不包含第 i-1 间房的方案也就是只考虑前 i-2 间房。这个约束是整个转移方程的“灵魂”写代码可以很快但面试官更想听到的是你能清楚解释这一步的因果关系。如果你采用下标不对齐的写法那方程就是dp[i] max(dp[i-1], dp[i-2] nums[i])初始化时dp[0] nums[0]dp[1] max(nums[0], nums[1])。两种写法本质上完全等价只是下标偏移不同。建议选定一种然后一直用下去不要今天写偏移一位明天写对齐下标的刷题时最容易在这种地方内耗。2.3 初始化与下标边界最容易翻车的地方House Robber 这种一维 DP 题真正决定你能不能一次性通过的不是转移方程而是初始化和循环边界。先说最简单的特判如果nums为空一间房都没有最大金额当然是 0如果nums长度为 1只有一间房只能偷它返回nums[0]。这两条不做的话后面的代码很可能会访问不存在的下标。如果你采用“dp[i]表示前 i 间房”的偏移写法那么dp数组长度应该申请为n 1。初始值设置两个dp[0] 0表示没有房屋时的收益dp[1] nums[0]表示只有第一间房时只能偷它。循环从i 2开始一直算到i n返回dp[n]。这种写法下dp[i-1]和dp[i-2]在循环里都不会越界因为 i 最小是 2i-2 最小是 0正好落在合法区间内。如果你采用下标对齐的写法dp数组长度为n那就要单独处理dp[0] nums[0]dp[1] max(nums[0], nums[1])循环从i 2开始。这里就有个坑如果n 1访问nums[1]就会直接数组越界所以必须先判断 n 是否为 1。很多人在 LeetCode 上第一次提交失败就是栽在这一行。还有一种更滑头的写法也是我后来最常用的不申请数组直接用两个滚动变量。初始化prev2 0prev1 0然后遍历每个数num计算cur max(prev1, prev2 num)再更新prev2 prev1prev1 cur。这种写法天然处理了 n0 和 n1 的情况因为 n0 时循环不执行返回prev1 0n1 时执行一次cur max(0, 0 nums[0]) nums[0]。可以说它是所有写法里最优雅、最不容易出错的。这个我在下一章展开讲。3. 代码实现与空间优化从记忆化搜索到滚动变量3.1 先写暴力递归理解问题规模很多解法文章上来就给动态规划代码但我个人经验是如果你对 DP 不熟第一版应该先写暴力递归。它未必能通过力扣的测试但能帮你理清决策树。暴力递归的思路是对于第 i 间房依然是两个选择。偷它那么下一间就得跳过不偷它就直接看下一间。写成函数就是def rob(nums): def dfs(i): if i 0: return 0 # 偷第 i 间收益是 nums[i] dfs(i-2) # 不偷第 i 间收益是 dfs(i-1) return max(dfs(i - 1), dfs(i - 2) nums[i]) return dfs(len(nums) - 1)这段代码非常直白几乎就是题目描述的翻译。但它的时间复杂度是 O(2^n)因为每个节点都会分叉成两个子问题递归树以指数速度膨胀。当 n30 左右时运行时间已经没法接受了。不过它给后续优化提供了很好的起点我们只要观察递归树就会发现大量子问题被重复计算比如dfs(i-2)既可能来自dfs(i)的分支也可能来自dfs(i-1)的分支。这就是动态规划里的“重叠子问题”。3.2 记忆化搜索给递归加缓存既然存在重复计算最简单粗暴的优化就是加一个缓存把算过的结果记下来。这叫记忆化搜索也叫自顶向下的动态规划。def rob(nums): 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 之后每个下标最多被计算一次时间复杂度立刻降到 O(n)空间复杂度 O(n)。从递归树的角度看我们保留了树的“结构”但剪掉了所有重复的子树计算。很多高手喜欢用这种写法因为它的思路和暴力递归一脉相承写错概率低而且能直观看到状态间依赖关系。不过记忆化搜索也有缺点。一是递归深度受限于 Python 默认的递归上限n 很大时会报RecursionError二是它的常数比迭代 DP 大面试时虽然能过但总显得不够干脆。所以下一步我们要把它改成自底向上的迭代写法这才是标准答案。3.3 标准 DP 数组版本根据第 2 章的状态定义和转移方程可以写出一个清晰的一维 DP 数组版本。我下面分别给出 Python 和 C 两种实现。def rob(nums): n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[n - 1]int rob(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint dp(n, 0); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] max(dp[i - 1], dp[i - 2] nums[i]); } return dp[n - 1]; }注意这个版本用的是“下标对齐”的写法所以必须有前面的特判。作为对比我再用“前 i 间房”的偏移写法写一遍你会发现边界处理会自然很多def rob(nums): n len(nums) if n 0: return 0 dp [0] * (n 1) dp[1] nums[0] # 前 1 间房只能偷第 1 间 for i in range(2, n 1): dp[i] max(dp[i - 1], dp[i - 2] nums[i - 1]) return dp[n]这个版本里dp[0]天然是 0不需要单独给dp[1]写max(nums[0], nums[1])。循环从 2 到 n每次用nums[i-1]取当前房的金额逻辑非常统一。如果你的代码要给别人看或者你自己容易在边界上翻车我强烈建议用这种偏移写法。3.4 滚动数组优化把空间压到 O(1)观察转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你很快会意识到计算dp[i]时真正需要的只有前两个状态dp[i-1]和dp[i-2]更早的dp[0]、dp[1]等等都用不上了。那我们完全没必要开一个长度为 n 的数组只需要两个变量把最近两个状态存下来边遍历边更新。这就是众所周知的“滚动数组”优化。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这个版本堪称一维 DP 的“最优解”。它不仅空间复杂度降到 O(1)还免去了所有特判空数组直接返回 0单元素数组执行一次循环后返回该元素。很多初学者看到这个写法觉得很神奇其实它就是把 DP 数组压缩成了两个滚动变量。面试时我通常会先写数组版本等面试官问“还能优化吗”再展示这个版本顺便讲清楚它为什么正确。这里有一个非常容易写错的细节更新的顺序。prev2 prev1必须在prev1 cur之前否则你会把新的prev1覆盖进prev2导致下一次循环少了一个状态。我自己早期写过一次反向更新的 Bug当时查了半天才发现是两个变量赋值顺序反了。后来我总结了一个口诀“先丢最旧再更新最新”。prev2是最旧的状态先让位prev1再上位逻辑才不会乱。3.5 从“打家劫舍”到“最少硬币”这类一维 DPHouse Robber 的价值在于它代表了一大类一维 DP 问题的通用解法框架状态数组表示“考虑前 i 个元素时的最优值”转移时在“选当前元素”和“不选当前元素”之间取最值。这个框架适用范围非常广。比如动态规划里另一道经典题“零钱兑换”状态定义是dp[amount]表示凑出 amount 所需的最少硬币数转移时枚举最后一枚硬币面额dp[amount] min(dp[amount - coin] 1)本质上也是在“选择哪种硬币作为最后一步”之间取最值。再比如爬楼梯dp[i] dp[i-1] dp[i-2]可以理解为状态只依赖前两个状态所以同样可以用滚动数组优化成 O(1) 空间。还有“使用最小花费爬楼梯”状态转移也是标准的“从上一个台阶过来还是从上上一个台阶过来”的二选一。我把这类题统称为“位置型一维 DP”。它们的共同特征就是当前状态只和前面的若干状态相关而且转移时要么取最大值要么取最小值要么做累加。把 House Robber 的“状态定义 转移方程 滚动数组”这套组合拳练熟再去做哈希表、双指针之外的其他动态规划题你会发现自己识别题目模式的速度明显变快。这就是为什么 LeetCode 热题 100 里它总被放在动态规划专题靠前的位置也是它被各种刷题清单反复推荐的原因。4. 常见问题与排查技巧实录4.1 为什么我的答案比预期小很多人第一次写 House Robber自测示例过了一提交就发现某些用例答案不对而且偏偏是答案偏小。这种问题多半出在转移方程写成了dp[i] max(dp[i-1], dp[i-2] nums[i-1])时把dp[i-1]这个“不偷当前房屋”的分支丢了或者写成了dp[i] dp[i-2] nums[i-1]以为必须隔一家偷一家。要检查这个问题用一组反例验证即可nums [2, 1, 1, 2]。正确答案是偷第 1 间和第 4 间2 2 4。如果你写的是必须隔一间偷那只能偷第 1、3 间或者第 2、4 间最多 3。跑一下这个用例立刻就能发现转移方程有没有丢掉“不偷”分支。实际上dp[i]总是不小于dp[i-1]的因为所有非负金额下前 i 间房的最优解至少不会差于前 i-1 间房的最优解。如果你的结果出现下降趋势基本可以断定方程写错了。4.2 为什么一运行就数组越界数组越界有一半以上是 n0 或 n1 的特判没写。比如你采用下标对齐的写法如果n1代码执行到dp[1] max(nums[0], nums[1])时直接访问了不存在的nums[1]运行立刻报错。解决办法有两个要么在开头加上if n 0: return 0和if n 1: return nums[0]要么改用“前 i 间房”的偏移写法配合滚动数组让代码天然规避掉这些特判。还有一种隐蔽的越界发生在循环结束条件写错。比如偏移写法应该for i in range(2, n 1)如果写成range(2, n)最后一间房不会被考虑结果自然不对虽然不会报错。这类问题最好通过多组测试去发现尤其是数组长度为 1、2、3 的小用例挨个跑一遍能省下很多调试时间。4.3 “不能偷相邻两家”不等于“必须隔一家偷一家”这个问题值得单独拿出来说因为它直接关系到对题意的理解。题目说的是“相邻的两间房不能同时偷”也就是任意两个被选中的房子之间至少要隔一个位置但隔几个完全自由。所以被偷的房子之间可以空一间也可以空两间、空三间。很多人下意识把“不能相邻”脑补成了“必须间隔固定的一家”这就把原题限制死了。用前面反复出现的反例[2, 1, 1, 2]能直观说明最优解选择的第 1 间和第 4 间之间隔了两间房而不是一间。如果你脑子里始终是“隔一家偷一次”的固定间隔那么看到这样的用例就会懵。理解这一点之后再回头推转移方程你就能明白为什么偷当前房时要看dp[i-2]而不是固定减 2 再减 2因为dp[i-2]本身已经包含了“前 i-2 间房内部怎么选都不违反约束”的所有最优信息它不一定恰好偷了第 i-2 间可能中间还空了更多房间。这就是 DP 比固定模式聪明的地方。4.4 面试官为什么总追问“能不能优化空间”House Robber 在面试里出现频率很高不是因为题目难而是它可以一层层追问考察候选人对 DP 的理解深度。通常对话是这样的候选人写出 O(n) 时间、O(n) 空间的 DP 解法之后面试官会问“能不能把空间复杂度优化到 O(1)”。如果候选人能答出用两个滚动变量取代整个数组面试官会继续问“为什么可以这样优化”这时候你要点出关键转移方程只依赖前两个状态更早的状态不再参与后续计算所以可以被丢弃。这个理由不仅适用于本题也适用于任何“依赖有限历史状态”的 DP 问题。如果再往深里问可能会延伸到环形数组版打家劫舍 II把环拆成两条链分别求[0, n-2]和[1, n-1]的结果再取最大值。这其实就是对“如何把非常规结构转化为常规一维 DP”的考察。所以我建议准备面试时不仅要把基础版写顺还要顺带把打家劫舍 II 的拆环思路想一遍这样遇到追问不会慌。4.5 自测用例速查表我在本地调试时一般会准备这样一组用例覆盖绝大多数边界情况。这里整理成表格方便你直接抄去自测。输入 nums预期输出说明[]0空数组特判[5]5只有一个元素[1, 2]2两个元素取最大值[2, 1, 1, 2]4隔两间偷更好验证核心约束[2, 7, 9, 3, 1]12官方示例[1, 3, 1, 3, 100]103取第2间和最后一间[0, 0, 0, 0]0全零金额这些用例覆盖了“空输入”“单元素”“双元素”“隔多间”“全零”等常见坑点。我的习惯是写完代码先跑一遍表格里的用例再提交到力扣基本能避开 80% 的 WA。剩下 20% 一般是转移方程写错导致的大数据量用例不通过那就回到第 4.1 节去检查“不偷”分支是否被丢弃。5. 从一维DP到刷题方法论House Robber 之后该怎么练5.1 House Robber 在力扣热题100中的位置House Robber 在力扣上是第 198 题也是“力扣热题 100”中动态规划分类的常驻成员。很多刷题攻略把它列为动态规划必刷的第一题或第二题排在爬楼梯之后。原因很简单它的状态定义非常自然转移方程不复杂但包含了 DP 最核心的要素。只要把这道题吃透后面再碰到类似的“选择与不选择”模型都会很顺。我个人的看法是这道题对新手最大的价值在于它提供了一个“一维 DP 的最小完备示例”。什么叫最小完备就是状态、转移、初始化、优化四个环节它全都有而且每个环节都不绕弯子。很多 DP 题要么状态维度高要么转移有多个分支要么需要额外数据结构辅助像 House Robber 这样干净利落、又能一次性讲完所有 DP 基础概念的题其实不多。所以无论你是在 LeetCode 上按题号顺序刷还是按专题刷我都建议把这一题放在 DP 专题的最前面。5.2 相关扩展题与一维 DP 刷题顺序刷完 House Robber 之后不要急着往难题冲先把同一类的一维 DP 题串起来练效果会更好。我根据自己的刷题经验整理了一个推荐顺序。第一步做爬楼梯70、使用最小花费爬楼梯746。这两道题和 House Robber 共享同一个结构都是当前位置的答案由前两个位置推导差别只在于一个是计数一个是最值转移方程极其相似。练完它们你对“依赖前两个状态”的模型就有了肌肉记忆。第二步做打家劫舍 II213。它把线性数组变成了环形数组核心技巧是拆环。做法很简单因为首尾不能同时偷所以分两种情况一种是不考虑最后一间一种是不考虑第一间分两次跑 House Robber 的解法取最大值。这个题考察的就是你能不能灵活地把未知问题转化为已知问题。第三步做打家劫舍 III337。这一题从一维数组升级成了二叉树DP 状态也从一个数值变成了“偷当前节点”和“不偷当前节点”两个状态配合树的递归遍历。它能帮你理解 DP 不一定是“数组 for 循环”树形结构一样可以做状态转移。刷到这里你对 House Robber 整个系列的掌握就比较完整了。第四步往更广的一维 DP 扩展零钱兑换322、最长递增子序列300、单词拆分139。这些题虽然不再是简单的“选/不选相邻”但它们的核心思路依然是一维 DP 的变体区别主要在于状态定义和转移来源。有了 House Robber 打底你再看它们会更容易抓住重点。5.3 我的刷题心得先写两句话再写代码写算法题最忌讳拿到题就开写代码尤其是 DP 题。我给自己定过一个规矩遇到动态规划题先在本子上写两句话第一句是“dp[i] 表示什么”第二句是“dp[i] 从哪些更小的状态转移过来”。只要这两句话能写清楚代码就是翻译工作。House Robber 的这两句话分别是“dp[i] 表示前 i 间房能偷到的最大金额”“dp[i] max(dp[i-1], dp[i-2] nums[i-1])”。就这么简单。很多想不明白的问题比如“为什么初始化 dp[0]0”“为什么循环从 2 开始”在写这两句话的时候都会自动暴露出来。如果这两句话写不出来说明你对题目的理解还不够透彻这时候写代码只能是碰运气。另一个心得是别怕把简单题做复杂。我见过不少人觉得 House Robber 太简单直接跳过结果在打家劫舍 II 上卡很久。其实简单题正是建立“手感”的时机把转移方程、边界条件、空间优化这三个基本功练扎实后面遇到包装得花哨的难题你才能一眼看穿它的本质。LeetCode 刷题数量固然重要但质量更重要一道 House Robber 能讲清楚、写干净、还会扩展三种变体胜过机械地刷十道类似的题。最后再分享一个小技巧刷 DP 题时试着把滚动数组版本也写一遍。不要觉得那是“炫技”它能强迫你理解每个变量的含义。以 House Robber 为例prev2和prev1在每一轮迭代前后分别是什么状态如果你能用一个具体的小数组把变量的变化过程推演一遍那这题对你来说就真正结束了。
力扣 198 题 House Robber也就是“打家劫舍”在算法题圈子里几乎人人刷过。它被归为“动态规划”分类而且是最标准的一维动态规划模板。题目本身非常简单一排房子每间房里有金额不等的现金你不能偷相邻两间问一晚上最多能偷多少。但就是这么一道简单题我在面试候选人、也在我自己反复刷题的过程中发现很多人能背出答案却讲不清楚状态为什么这样定义、转移方程为什么是dp[i] max(dp[i-1], dp[i-2] nums[i])更不用说在 n1 或者空数组这种边界条件下翻车。所以这篇笔记不打算只贴一段能通过的代码而是把“一维动态规划”从暴力递归到记忆化搜索再到标准 DP 数组、滚动数组优化这条完整路径拆开讲透。不管你是刚开始刷 LeetCode 的初学者还是在准备面试想把这类型题说得更有条理这篇都值得耐心读完。写完之后你会发现House Robber 不仅仅是“力扣热题 100”里的一道简单题它几乎是一维 DP 所有重要概念的浓缩状态定义、转移方程、边界条件、空间压缩。把这题吃透后面再碰到零钱兑换、爬楼梯、跳跃游戏这类一维 DP 题思路会顺畅很多。1. 题目理解与解题思路为什么“隔一家偷一次”靠不住1.1 先读懂题目别急着写代码House Robber 的题目描述很直观你是一个专业小偷计划偷窃沿街的房屋。每间房内藏有一定现金影响你作案的关键约束是如果两间相邻的房屋在同一晚上被闯入会惊动安保系统。也就是说你不能偷相邻的两间房。给定一个非负整数数组nums其中nums[i]代表第 i 间房里的金额要求计算出不触发警报的前提下你今晚能偷到的最大金额。把它抽象成纯算法问题就是给定一个非负整数数组选出一个子序列要求子序列中任意两个元素在原始数组中不相邻求这个子序列的元素和最大值。举个人人都能看懂的示例。比如nums [1, 2, 3, 1]最优方案是偷第 1 间和第 3 间也就是 1 3 4。如果你偷第 2 间和第 4 间得到 2 1 3不如前者。再比如nums [2, 7, 9, 3, 1]最优方案是偷第 1、3、5 间即 2 9 1 12而不是简单地把奇数位全部加起来或者偶数位全部加起来就完事。为什么不是 7 3 10因为那只是“隔一家偷一次”的其中一种固定模式并不是最优。我经常和刷题的人说拿到这种题第一件事不是想“能不能贪心”而是先把问题用数学语言重新描述一遍。数组、子序列、求最值这三个关键词凑在一起动态规划就是非常自然的候选方案。这里最核心的操作是“选或不选”对于每一间房你只有两个选择偷它或者不偷它。一旦确定了这间房是否偷相邻房屋的可行性就受到了限制。这种“当前决策影响后续选择空间”的模型恰好是动态规划最擅长的场景之一。1.2 贪心思路为什么不行很多人第一次看到这道题会冒出一个直觉既然不能偷相邻的那我就隔一家偷一家或者我每次都偷当前能偷的最大金额。这两种直觉都是典型的贪心思路可惜都不成立。先说说“隔一家偷一家”的问题。它隐含假设了被偷的房子之间必须恰好空一个房间但题目只要求“不相邻”完全没有说不能隔两间、隔三间。看一个反例nums [2, 1, 1, 2]。按“隔一家偷一家”来算偷第 1、3 间得到 2 1 3但如果偷第 1、4 间得到 2 2 4这一步直接空了两间房结果反而更大。这说明最优解里被跳过的房屋数是不固定的不能用一个简单的固定间隔概括。再说说“每次取当前最大可偷金额”的策略。举个反例nums [3, 2, 3, 2, 3]。如果你第一间就选择了最大的 3那么第二间被锁死不能选之后你只能在第三间和第五间里再选比如偷第一间和第三间、或者第一间和第五间最多也就 6。但如果你放弃第一间转而偷第二间和第四间得到 2 2 4也不是最好。最优是偷第一间、第三间、第五间3 3 3 9。这里问题在于单看某一间很大不代表选了它之后整条路径最优因为它会封死旁边一间原本可能更优的选择。贪心失败的根本原因在于局部最优无法推出全局最优。当前房间中金额大的不一定是最终路径的一部分你可能为了一个比较大的值失去了右侧连续更优的组合。遇到这种“每个位置做选择选择之间有约束要求全局最值”的模型应该立刻想到动态规划而不是在贪心的死胡同里继续优化。1.3 动态规划为什么合适动态规划之所以适合本题是因为它天然具备两个关键性质。第一个是最优子结构。假设我们已经知道前 i-1 间房能偷到的最大金额是dp[i-1]前 i-2 间房能偷到的最大金额是dp[i-2]那么对于第 i 间房我们只需要在这个两个信息基础上再做一次比较就能得到前 i 间房的最优值。当前房间偷还是不偷这两个分支都已经可以被之前的子问题完整描述。第二个是无后效性。在状态转移时我们只关心“前 i 间房最多能偷多少”而不需要关心到底偷了哪几间、最后一间是不是偷了。因为题目只限制相邻关系已经偷过的房屋只会影响“下一间能不能偷”这一个事实而不会影响更久远的选择。把历史信息压缩成dp数组里的一个数值就是无后效性的直接体现。从这两个性质出发一维 DP 的骨架就出来了一个一维数组dp其中dp[i]表示前 i 间房或者说考虑下标从 0 到 i 的这些房屋能偷到的最大金额。有了这个定义接下来的问题就是怎么从dp[i-1]、dp[i-2]推出dp[i]也就是传说中的状态转移方程。这个过程像搭积木每一块都在前两块的基础上选择最优路径最后拼出全局答案。2. 状态设计与状态转移方程一维DP的关键细节2.1 状态定义怎么写最不容易错动态规划题最怕的不是转移方程写不出来而是状态定义一开始就写得含糊。House Robber 里最常见的状态定义有两种写法我分别说一下它们的区别和适用场景。第一种写法是dp[i]表示“考虑前 i 间房屋时能偷到的最大金额”下标从 1 开始对应第 1 间房。这种写法下dp[0]表示没有房屋时的最大金额自然为 0dp[1] nums[0]表示只有一间房时只能偷它。用这种方式定义时代码里的循环可以从 i1 一直扫描到 n边界处理相对统一非常推荐。第二种写法是dp[i]表示“从 0 到 i 这 i1 间房屋中以第 i 间房屋为结尾考虑时能得到的最大金额”也就是下标直接和原数组对齐。这种写法在代码里更常见但你必须单独处理 i0 和 i1 的初始化循环还得从 2 开始下标细节特别容易写错。我个人更推荐把下标错开一位的写法也就是让dp[i]对应“前 i 个房屋”其中dp[0]天然表示空集。这样有几个好处不需要对数组长度做特殊判断代码逻辑统一转移时dp[i-1]、dp[i-2]不会出现负下标问题后续如果扩展到打家劫舍 II、打家劫舍 III这种“多了一个空位”的定义方式也更方便处理环形和树形结构。很多一线工程师写 DP 题也倾向于这种偏移一位的写法就是因为它能把边界坑减少一大半。无论是哪种定义方式建议你在写代码前先在注释里写清楚一句话“dp[i]代表什么”。这一句话写清楚了后面的转移方程、初始化、返回值就都有了依据。很多人在刷题时省略这一步结果写着写着下标就乱了再回来改状态定义往往比重新写一遍还费时间。2.2 转移方程推导选与不选的二选一状态定义确定后转移方程其实是顺水推舟。我们站在第 i 间房屋面前面临两个选项。选项一不偷第 i 间房。那么第 i-1 间房偷不偷都无所谓结果直接等于前 i-1 间房的最优解也就是dp[i-1]。选项二偷第 i 间房。一旦偷了这一间第 i-1 间房绝对不能偷所以我们能用的最优方案来自前 i-2 间房再加上当前这间的金额nums[i-1]因为下标偏移了一位第 i 间房对应nums[i-1]也就是dp[i-2] nums[i-1]。综合起来转移方程就是dp[i] max(dp[i-1], dp[i-2] nums[i-1])这里有个初学者最容易犯错的地方就是为什么偷第 i 间时用的是dp[i-2]而不是dp[i-1]。原因是你不能偷相邻的两间房。如果偷了第 i 间那么第 i-1 间就一定不能偷所以前面能沿用的最优解必须是不包含第 i-1 间房的方案也就是只考虑前 i-2 间房。这个约束是整个转移方程的“灵魂”写代码可以很快但面试官更想听到的是你能清楚解释这一步的因果关系。如果你采用下标不对齐的写法那方程就是dp[i] max(dp[i-1], dp[i-2] nums[i])初始化时dp[0] nums[0]dp[1] max(nums[0], nums[1])。两种写法本质上完全等价只是下标偏移不同。建议选定一种然后一直用下去不要今天写偏移一位明天写对齐下标的刷题时最容易在这种地方内耗。2.3 初始化与下标边界最容易翻车的地方House Robber 这种一维 DP 题真正决定你能不能一次性通过的不是转移方程而是初始化和循环边界。先说最简单的特判如果nums为空一间房都没有最大金额当然是 0如果nums长度为 1只有一间房只能偷它返回nums[0]。这两条不做的话后面的代码很可能会访问不存在的下标。如果你采用“dp[i]表示前 i 间房”的偏移写法那么dp数组长度应该申请为n 1。初始值设置两个dp[0] 0表示没有房屋时的收益dp[1] nums[0]表示只有第一间房时只能偷它。循环从i 2开始一直算到i n返回dp[n]。这种写法下dp[i-1]和dp[i-2]在循环里都不会越界因为 i 最小是 2i-2 最小是 0正好落在合法区间内。如果你采用下标对齐的写法dp数组长度为n那就要单独处理dp[0] nums[0]dp[1] max(nums[0], nums[1])循环从i 2开始。这里就有个坑如果n 1访问nums[1]就会直接数组越界所以必须先判断 n 是否为 1。很多人在 LeetCode 上第一次提交失败就是栽在这一行。还有一种更滑头的写法也是我后来最常用的不申请数组直接用两个滚动变量。初始化prev2 0prev1 0然后遍历每个数num计算cur max(prev1, prev2 num)再更新prev2 prev1prev1 cur。这种写法天然处理了 n0 和 n1 的情况因为 n0 时循环不执行返回prev1 0n1 时执行一次cur max(0, 0 nums[0]) nums[0]。可以说它是所有写法里最优雅、最不容易出错的。这个我在下一章展开讲。3. 代码实现与空间优化从记忆化搜索到滚动变量3.1 先写暴力递归理解问题规模很多解法文章上来就给动态规划代码但我个人经验是如果你对 DP 不熟第一版应该先写暴力递归。它未必能通过力扣的测试但能帮你理清决策树。暴力递归的思路是对于第 i 间房依然是两个选择。偷它那么下一间就得跳过不偷它就直接看下一间。写成函数就是def rob(nums): def dfs(i): if i 0: return 0 # 偷第 i 间收益是 nums[i] dfs(i-2) # 不偷第 i 间收益是 dfs(i-1) return max(dfs(i - 1), dfs(i - 2) nums[i]) return dfs(len(nums) - 1)这段代码非常直白几乎就是题目描述的翻译。但它的时间复杂度是 O(2^n)因为每个节点都会分叉成两个子问题递归树以指数速度膨胀。当 n30 左右时运行时间已经没法接受了。不过它给后续优化提供了很好的起点我们只要观察递归树就会发现大量子问题被重复计算比如dfs(i-2)既可能来自dfs(i)的分支也可能来自dfs(i-1)的分支。这就是动态规划里的“重叠子问题”。3.2 记忆化搜索给递归加缓存既然存在重复计算最简单粗暴的优化就是加一个缓存把算过的结果记下来。这叫记忆化搜索也叫自顶向下的动态规划。def rob(nums): 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 之后每个下标最多被计算一次时间复杂度立刻降到 O(n)空间复杂度 O(n)。从递归树的角度看我们保留了树的“结构”但剪掉了所有重复的子树计算。很多高手喜欢用这种写法因为它的思路和暴力递归一脉相承写错概率低而且能直观看到状态间依赖关系。不过记忆化搜索也有缺点。一是递归深度受限于 Python 默认的递归上限n 很大时会报RecursionError二是它的常数比迭代 DP 大面试时虽然能过但总显得不够干脆。所以下一步我们要把它改成自底向上的迭代写法这才是标准答案。3.3 标准 DP 数组版本根据第 2 章的状态定义和转移方程可以写出一个清晰的一维 DP 数组版本。我下面分别给出 Python 和 C 两种实现。def rob(nums): n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[n - 1]int rob(vectorint nums) { int n nums.size(); if (n 0) return 0; if (n 1) return nums[0]; vectorint dp(n, 0); dp[0] nums[0]; dp[1] max(nums[0], nums[1]); for (int i 2; i n; i) { dp[i] max(dp[i - 1], dp[i - 2] nums[i]); } return dp[n - 1]; }注意这个版本用的是“下标对齐”的写法所以必须有前面的特判。作为对比我再用“前 i 间房”的偏移写法写一遍你会发现边界处理会自然很多def rob(nums): n len(nums) if n 0: return 0 dp [0] * (n 1) dp[1] nums[0] # 前 1 间房只能偷第 1 间 for i in range(2, n 1): dp[i] max(dp[i - 1], dp[i - 2] nums[i - 1]) return dp[n]这个版本里dp[0]天然是 0不需要单独给dp[1]写max(nums[0], nums[1])。循环从 2 到 n每次用nums[i-1]取当前房的金额逻辑非常统一。如果你的代码要给别人看或者你自己容易在边界上翻车我强烈建议用这种偏移写法。3.4 滚动数组优化把空间压到 O(1)观察转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])你很快会意识到计算dp[i]时真正需要的只有前两个状态dp[i-1]和dp[i-2]更早的dp[0]、dp[1]等等都用不上了。那我们完全没必要开一个长度为 n 的数组只需要两个变量把最近两个状态存下来边遍历边更新。这就是众所周知的“滚动数组”优化。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这个版本堪称一维 DP 的“最优解”。它不仅空间复杂度降到 O(1)还免去了所有特判空数组直接返回 0单元素数组执行一次循环后返回该元素。很多初学者看到这个写法觉得很神奇其实它就是把 DP 数组压缩成了两个滚动变量。面试时我通常会先写数组版本等面试官问“还能优化吗”再展示这个版本顺便讲清楚它为什么正确。这里有一个非常容易写错的细节更新的顺序。prev2 prev1必须在prev1 cur之前否则你会把新的prev1覆盖进prev2导致下一次循环少了一个状态。我自己早期写过一次反向更新的 Bug当时查了半天才发现是两个变量赋值顺序反了。后来我总结了一个口诀“先丢最旧再更新最新”。prev2是最旧的状态先让位prev1再上位逻辑才不会乱。3.5 从“打家劫舍”到“最少硬币”这类一维 DPHouse Robber 的价值在于它代表了一大类一维 DP 问题的通用解法框架状态数组表示“考虑前 i 个元素时的最优值”转移时在“选当前元素”和“不选当前元素”之间取最值。这个框架适用范围非常广。比如动态规划里另一道经典题“零钱兑换”状态定义是dp[amount]表示凑出 amount 所需的最少硬币数转移时枚举最后一枚硬币面额dp[amount] min(dp[amount - coin] 1)本质上也是在“选择哪种硬币作为最后一步”之间取最值。再比如爬楼梯dp[i] dp[i-1] dp[i-2]可以理解为状态只依赖前两个状态所以同样可以用滚动数组优化成 O(1) 空间。还有“使用最小花费爬楼梯”状态转移也是标准的“从上一个台阶过来还是从上上一个台阶过来”的二选一。我把这类题统称为“位置型一维 DP”。它们的共同特征就是当前状态只和前面的若干状态相关而且转移时要么取最大值要么取最小值要么做累加。把 House Robber 的“状态定义 转移方程 滚动数组”这套组合拳练熟再去做哈希表、双指针之外的其他动态规划题你会发现自己识别题目模式的速度明显变快。这就是为什么 LeetCode 热题 100 里它总被放在动态规划专题靠前的位置也是它被各种刷题清单反复推荐的原因。4. 常见问题与排查技巧实录4.1 为什么我的答案比预期小很多人第一次写 House Robber自测示例过了一提交就发现某些用例答案不对而且偏偏是答案偏小。这种问题多半出在转移方程写成了dp[i] max(dp[i-1], dp[i-2] nums[i-1])时把dp[i-1]这个“不偷当前房屋”的分支丢了或者写成了dp[i] dp[i-2] nums[i-1]以为必须隔一家偷一家。要检查这个问题用一组反例验证即可nums [2, 1, 1, 2]。正确答案是偷第 1 间和第 4 间2 2 4。如果你写的是必须隔一间偷那只能偷第 1、3 间或者第 2、4 间最多 3。跑一下这个用例立刻就能发现转移方程有没有丢掉“不偷”分支。实际上dp[i]总是不小于dp[i-1]的因为所有非负金额下前 i 间房的最优解至少不会差于前 i-1 间房的最优解。如果你的结果出现下降趋势基本可以断定方程写错了。4.2 为什么一运行就数组越界数组越界有一半以上是 n0 或 n1 的特判没写。比如你采用下标对齐的写法如果n1代码执行到dp[1] max(nums[0], nums[1])时直接访问了不存在的nums[1]运行立刻报错。解决办法有两个要么在开头加上if n 0: return 0和if n 1: return nums[0]要么改用“前 i 间房”的偏移写法配合滚动数组让代码天然规避掉这些特判。还有一种隐蔽的越界发生在循环结束条件写错。比如偏移写法应该for i in range(2, n 1)如果写成range(2, n)最后一间房不会被考虑结果自然不对虽然不会报错。这类问题最好通过多组测试去发现尤其是数组长度为 1、2、3 的小用例挨个跑一遍能省下很多调试时间。4.3 “不能偷相邻两家”不等于“必须隔一家偷一家”这个问题值得单独拿出来说因为它直接关系到对题意的理解。题目说的是“相邻的两间房不能同时偷”也就是任意两个被选中的房子之间至少要隔一个位置但隔几个完全自由。所以被偷的房子之间可以空一间也可以空两间、空三间。很多人下意识把“不能相邻”脑补成了“必须间隔固定的一家”这就把原题限制死了。用前面反复出现的反例[2, 1, 1, 2]能直观说明最优解选择的第 1 间和第 4 间之间隔了两间房而不是一间。如果你脑子里始终是“隔一家偷一次”的固定间隔那么看到这样的用例就会懵。理解这一点之后再回头推转移方程你就能明白为什么偷当前房时要看dp[i-2]而不是固定减 2 再减 2因为dp[i-2]本身已经包含了“前 i-2 间房内部怎么选都不违反约束”的所有最优信息它不一定恰好偷了第 i-2 间可能中间还空了更多房间。这就是 DP 比固定模式聪明的地方。4.4 面试官为什么总追问“能不能优化空间”House Robber 在面试里出现频率很高不是因为题目难而是它可以一层层追问考察候选人对 DP 的理解深度。通常对话是这样的候选人写出 O(n) 时间、O(n) 空间的 DP 解法之后面试官会问“能不能把空间复杂度优化到 O(1)”。如果候选人能答出用两个滚动变量取代整个数组面试官会继续问“为什么可以这样优化”这时候你要点出关键转移方程只依赖前两个状态更早的状态不再参与后续计算所以可以被丢弃。这个理由不仅适用于本题也适用于任何“依赖有限历史状态”的 DP 问题。如果再往深里问可能会延伸到环形数组版打家劫舍 II把环拆成两条链分别求[0, n-2]和[1, n-1]的结果再取最大值。这其实就是对“如何把非常规结构转化为常规一维 DP”的考察。所以我建议准备面试时不仅要把基础版写顺还要顺带把打家劫舍 II 的拆环思路想一遍这样遇到追问不会慌。4.5 自测用例速查表我在本地调试时一般会准备这样一组用例覆盖绝大多数边界情况。这里整理成表格方便你直接抄去自测。输入 nums预期输出说明[]0空数组特判[5]5只有一个元素[1, 2]2两个元素取最大值[2, 1, 1, 2]4隔两间偷更好验证核心约束[2, 7, 9, 3, 1]12官方示例[1, 3, 1, 3, 100]103取第2间和最后一间[0, 0, 0, 0]0全零金额这些用例覆盖了“空输入”“单元素”“双元素”“隔多间”“全零”等常见坑点。我的习惯是写完代码先跑一遍表格里的用例再提交到力扣基本能避开 80% 的 WA。剩下 20% 一般是转移方程写错导致的大数据量用例不通过那就回到第 4.1 节去检查“不偷”分支是否被丢弃。5. 从一维DP到刷题方法论House Robber 之后该怎么练5.1 House Robber 在力扣热题100中的位置House Robber 在力扣上是第 198 题也是“力扣热题 100”中动态规划分类的常驻成员。很多刷题攻略把它列为动态规划必刷的第一题或第二题排在爬楼梯之后。原因很简单它的状态定义非常自然转移方程不复杂但包含了 DP 最核心的要素。只要把这道题吃透后面再碰到类似的“选择与不选择”模型都会很顺。我个人的看法是这道题对新手最大的价值在于它提供了一个“一维 DP 的最小完备示例”。什么叫最小完备就是状态、转移、初始化、优化四个环节它全都有而且每个环节都不绕弯子。很多 DP 题要么状态维度高要么转移有多个分支要么需要额外数据结构辅助像 House Robber 这样干净利落、又能一次性讲完所有 DP 基础概念的题其实不多。所以无论你是在 LeetCode 上按题号顺序刷还是按专题刷我都建议把这一题放在 DP 专题的最前面。5.2 相关扩展题与一维 DP 刷题顺序刷完 House Robber 之后不要急着往难题冲先把同一类的一维 DP 题串起来练效果会更好。我根据自己的刷题经验整理了一个推荐顺序。第一步做爬楼梯70、使用最小花费爬楼梯746。这两道题和 House Robber 共享同一个结构都是当前位置的答案由前两个位置推导差别只在于一个是计数一个是最值转移方程极其相似。练完它们你对“依赖前两个状态”的模型就有了肌肉记忆。第二步做打家劫舍 II213。它把线性数组变成了环形数组核心技巧是拆环。做法很简单因为首尾不能同时偷所以分两种情况一种是不考虑最后一间一种是不考虑第一间分两次跑 House Robber 的解法取最大值。这个题考察的就是你能不能灵活地把未知问题转化为已知问题。第三步做打家劫舍 III337。这一题从一维数组升级成了二叉树DP 状态也从一个数值变成了“偷当前节点”和“不偷当前节点”两个状态配合树的递归遍历。它能帮你理解 DP 不一定是“数组 for 循环”树形结构一样可以做状态转移。刷到这里你对 House Robber 整个系列的掌握就比较完整了。第四步往更广的一维 DP 扩展零钱兑换322、最长递增子序列300、单词拆分139。这些题虽然不再是简单的“选/不选相邻”但它们的核心思路依然是一维 DP 的变体区别主要在于状态定义和转移来源。有了 House Robber 打底你再看它们会更容易抓住重点。5.3 我的刷题心得先写两句话再写代码写算法题最忌讳拿到题就开写代码尤其是 DP 题。我给自己定过一个规矩遇到动态规划题先在本子上写两句话第一句是“dp[i] 表示什么”第二句是“dp[i] 从哪些更小的状态转移过来”。只要这两句话能写清楚代码就是翻译工作。House Robber 的这两句话分别是“dp[i] 表示前 i 间房能偷到的最大金额”“dp[i] max(dp[i-1], dp[i-2] nums[i-1])”。就这么简单。很多想不明白的问题比如“为什么初始化 dp[0]0”“为什么循环从 2 开始”在写这两句话的时候都会自动暴露出来。如果这两句话写不出来说明你对题目的理解还不够透彻这时候写代码只能是碰运气。另一个心得是别怕把简单题做复杂。我见过不少人觉得 House Robber 太简单直接跳过结果在打家劫舍 II 上卡很久。其实简单题正是建立“手感”的时机把转移方程、边界条件、空间优化这三个基本功练扎实后面遇到包装得花哨的难题你才能一眼看穿它的本质。LeetCode 刷题数量固然重要但质量更重要一道 House Robber 能讲清楚、写干净、还会扩展三种变体胜过机械地刷十道类似的题。最后再分享一个小技巧刷 DP 题时试着把滚动数组版本也写一遍。不要觉得那是“炫技”它能强迫你理解每个变量的含义。以 House Robber 为例prev2和prev1在每一轮迭代前后分别是什么状态如果你能用一个具体的小数组把变量的变化过程推演一遍那这题对你来说就真正结束了。
