打家劫舍这道题说它是动态规划入门阶段“必刷三件套”之一另外两个是爬楼梯和斐波那契数列一点也不夸张。原因很简单它把动态规划最核心的“状态定义”和“状态转移”展示得特别干净没有复杂的图论背景也没有冗余的数学公式一道题就能讲清楚DP的骨架。而它的第二问——打家劫舍II又把“环形数组如何拆解成线性问题”这个进阶技巧揉了进去很多人在这一版上栽过跟头。这篇文章就把这两道题从零到一拆开揉碎从状态定义到代码实现再到各类变形和踩坑记录一次讲透。1. 问题拆解先从最基础的打家劫舍I入手1.1 题目到底在说什么原题的描述很直白一排房子每间房里有不同数量的现金你是一个盗贼不能偷相邻的两间房否则会触发警报问一晚上最多能偷多少钱。这道题在很多面经里被称作“最大不相邻子序列和”问题本质上就是给定一个非负整数数组从中选取若干个不相邻的元素使得选取的元素之和最大。这个描述本身就藏着DP的两个关键特征决策有后效性影响今天偷不偷这一家直接影响明天能不能偷下一家子问题高度重复算到第 i 家时前面 i-1 家的最优结果是可以复用缓存的这两点恰恰是动态规划能派上用场的前提。1.2 暴力思路为什么走不通初学者第一反应大概率是枚举所有偷窃方案。比如有 n 间房每家都有“偷”和“不偷”两个选择但因为有“不能相邻”的限制方案数量虽然没有 2^n 那么多但指数级增长是跑不了的。我实测过n40 左右纯递归枚举就已经明显卡顿n50 以上基本要等到怀疑人生。递归枚举的代码长这样伪代码# 这种做法只适合理解题意千万别拿去交题 def solve(idx): if idx n: return 0 # 不偷当前这家 case1 solve(idx 1) # 偷当前这家那么下一家必须跳过 case2 nums[idx] solve(idx 2) return max(case1, case2)这段代码逻辑完全正确但存在严重的重叠子问题solve(4) 可能被 solve(2) 和 solve(1) 同时调用导致同一子问题被反复计算。不做剪枝的情况下时间复杂度是 O(φ^n)φ 是黄金分割比约 1.618也就是指数级。DP 要做的就是把这棵递归树给压扁用数组把子问题的答案存下来每个子问题只算一次。1.3 动态规划的状态定义打家劫舍 I 最经典的状态定义有两种我分别说一下因为它们在写代码时容易混淆。第一种dp[i] 表示“从第 0 间房到第 i 间房含第 i 间能偷到的最大金额”。那么当处理到第 i 间房时只有两种选择不偷第 i 间那么问题退化为 dp[i-1]偷第 i 间那么第 i-1 间不能偷问题退化为 dp[i-2] nums[i]于是状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])第二种dp[i] 表示“前 i 间房即第 0 到第 i-1 间能偷到的最大金额”。注意这里的下标含义变了dp[i] 对应的是前 i 间房不包含第 i 间。那么状态转移dp[i] max(dp[i-1], dp[i-2] nums[i-1])两种写法本质上一回事只是下标错位一位。很多人的 bug 都出在这个位差上所以强烈建议一种写法用到底不要混用。1.4 边界条件到底怎么定这是打家劫舍里最容易出错的点。如果用第一种定义dp[i] 表示到第 i 间为止的最大金额边界是dp[0] nums[0] # 只有一间房偷就完了 dp[1] max(nums[0], nums[1]) # 两间房只能二选一然后从 i2 开始遍历到 n-1。如果用第二种定义dp[i] 表示前 i 间房的最大金额边界是dp[0] 0 # 前 0 间房啥也没有当然是 0 dp[1] nums[0] # 前 1 间房就是第一间的钱然后从 i2 遍历到 n。我要特别强调一个细节边界这里很多人直接把 dp[0] 初始化为 nums[0]然后用 dp[i] max(dp[i-1], dp[i-2] nums[i]) 从 i1 开始跑这在只有一间房的情况下会数组越界因为需要访问 dp[-1]。所以最稳妥的做法是优先处理长度小于 2 的边界情况让主循环保持整洁。2. 打家劫舍 I 的代码实现与状态压缩2.1 标准DP解法的完整代码以第二种定义前 i 间房为准完整代码如下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]这段代码的时间复杂度是 O(n)空间复杂度是 O(n)。逐行拆解这段代码dp[i] 的更新只依赖 dp[i-1] 和 dp[i-2] 两个值这就是“滚动数组”能出场的信号。2.2 滚动数组压缩空间复杂度空间压缩其实非常简单因为每一步只需要前两个状态def rob(nums): prev2 0 # dp[i-2] prev1 0 # dp[i-1] for num in nums: current max(prev1, prev2 num) prev2 prev1 prev1 current return prev1这段代码我刚接触时觉得有点“魔术”因为它省略了 dp 数组的下标但跑一遍就通了。这里的关键是理解 prev1 和 prev2 的更新顺序current 计算完后原来的 prev1 变成了新的 prev2current 变成了新的 prev1。顺序不能反反了就会用已经更新过的值结果全错。我说一个生活化的类比这就像你手里始终只保留两张旧报价单——一张是“上一家能拿到的最高价”一张是“上上家能拿到的最高价”每次来一家新报价拿这两张单子算一下新结果然后把最旧的那张扔掉。无论店家有几百家你手里永远只有两张单子这就是 O(1) 空间的本质。2.3 复杂度分析打家劫舍 I 的复杂度没有悬念时间复杂度 O(n)每个房子扫描一次空间复杂度 O(1) 或 O(n)取决于是否使用滚动数组在几乎所有在线评测系统中打家劫舍 I 的 n 上限一般是 100 或 1000 这个量级所以哪怕不用滚动数组也绝不会超时。但在面试里主动写出滚动数组版本通常意味着你已经理解了状态转移的本质而不只是背了题解。3. 进阶打家劫舍 II 的环状结构处理3.1 题目变化在哪里打家劫舍 II 在 I 的基础上加了一个条件这些房子围成了一个环形也就是说第一间房和最后一间房现在变成了邻居。放到真实场景里就很好理解一条街变成了一圈盗贼从任意一家开始绕一圈首尾相接第一家和最后一家不能都偷。除此之外其他规则和 I 完全一致不能偷相邻两间。这一改看起来只是加了一个约束实际上直接把 I 的解法打了一个洞如果沿用 I 的线性 DP你可能会同时选中第 0 家和第 n-1 家这在环上不合法。3.2 环形问题的经典处理思路处理环形数组问题江湖上有两种通用套路第一种是“分类讨论法”也是打家劫舍 II 的主流解法。既然第 0 间和第 n-1 间不能同时被偷那我们就分两种情况不偷第 0 间问题退化为从第 1 间到第 n-1 间的线性打家劫舍不偷第 n-1 间问题退化为从第 0 间到第 n-2 间的线性打家劫舍取这两种情况的最大值就是答案。为什么这样分是完备的因为最优方案里第 0 间要么被偷了要么没被偷如果被偷了则第 n-1 间必然没被偷对应“不偷第 n-1 间”的情况如果没被偷那第 n-1 间偷不偷都行对应“不偷第 0 间”的情况所以这两种情况覆盖了所有合法的偷窃方案不多不漏。这就是分类讨论的完备性证明面试里能讲出来会很加分。第二种处理环形数组的思路是“复制一倍数组”把环形展开成 2n 长度的线性数组然后限制窗口长度为 n 来求解。但这种方法在打家劫舍 II 里不如分类讨论清爽因为复制一倍之后如何保证选出的方案不跨越环形边界也是个麻烦问题。所以实战中打家劫舍 II 基本都用分类讨论。3.3 具体代码实现在写代码之前有一个小坑必须先排掉n1 的情况。当只有一间房时“不偷第 0 间”和“不偷最后一间”这两种拆分都会得到一个空数组取最大值会得到 0但正确答案明明是 nums[0]。所以必须先特判 n 1。完整代码def rob(nums): n len(nums) if n 1: return nums[0] # 线性打家劫舍辅助函数偷 nums[l:r]左闭右开区间 def rob_range(l, r): prev2 0 # dp[i-2] prev1 0 # dp[i-1] for i in range(l, r): current max(prev1, prev2 nums[i]) prev2 prev1 prev1 current return prev1 # 情况1不偷第0间 - 范围 [1, n) case1 rob_range(1, n) # 情况2不偷最后一间 - 范围 [0, n-1) case2 rob_range(0, n - 1) return max(case1, case2)注意 rob_range 的左闭右开设计rob_range(1, n) 表示从下标 1 到 n-1不含 nrob_range(0, n-1) 表示从下标 0 到 n-2不含 n-1。这个区间设计是刻意为之的能完美避开边界 1/-1 的混乱。3.4 为什么这样拆分不会漏解我再用一个更形式化的方式描述一次方便你在需要时给别人讲清楚。设原环形数组为 nums[0 .. n-1]线性打家劫舍函数为 L(st, ed)表示只考虑从 st 到 ed-1 这个连续区间内的房子忽略其他房子。那么环形问题的最优解best max( L(1, n), L(0, n-1) )前一个 L(1, n) 的下标范围不含 0保证了第一间一定不偷后一个 L(0, n-1) 不含 n-1保证了最后一间一定不偷。从集合论角度看所有合法方案集合分为两类不含 0 的方案、不含 n-1 的方案这两类方案的并集覆盖了全集。所以取两个子集的并集的最大值一定等于全集的全局最大值。这个推理在数学上很干净没有任何缺口。我在面试中把这段讲出来后经常能看到面试官点头——因为它比单纯背代码有价值得多。4. 常见变形与容易踩的坑4.1 打家劫舍 III从数组变成树既然打家劫舍 I 和 II 都排干净了我顺手提一下系列里的第三题——打家劫舍 III因为如果你在刷题大概率这几天内就会遇到它。第三题把房子结构从一维数组/环形数组升级成了二叉树直接相邻的两个节点父子关系不能都被偷。这等于把DP从数组搬到了树上解法也从“数组递推”变成了“树形DP”。核心思路是每个节点维护两个状态偷这个节点时子树能获得的最大金额等于左右孩子“不偷”状态之和 当前节点值不偷这个节点时子树能获得的最大金额等于左右孩子各自最优状态之和每个孩子取偷或不偷的较大值这其实体现了DP的一个大方向状态定义跟着数据结构走。数组就用线性递推环形就拆线性树就递归后序遍历。理解了这条主线后面刷树形DP时会顺畅很多。4.2 隐藏条件金额可能是 0打家劫舍问题里有个约定俗成的设定每间房里的金额是非负整数。如果金额允许负数那“不偷任何一间”可能是最优解收益为 0但题目语义不允许这种场景——毕竟题目设定是“每间房都有一定数量的现金”非负合理。但在某些变体题里输入可能包含 0。比如 [0, 0, 1, 0, 0]这完全合法你的DP也必须正确处理。好消息是只要初始化的 prev2 0、prev1 0金额为 0 的房子不会产生任何影响代码自然能应对。4.3 滚动数组的常见错误我再单独强调一次滚动数组的更新顺序因为这是我见过新人栽得最多的地方# 错误写法 prev2 prev1 prev1 max(prev1, prev2 num)这个错误版本在计算新的 prev1 时用的 prev2 其实已经被更新为旧的 prev1等于 max 的两个参数都来自同一层DP 退化成“只允许连续偷”的错误逻辑结果完全跑偏。正确写法current max(prev1, prev2 num) prev2 prev1 prev1 current这两个顺序差的只是两行代码的先后但语义差了一个维度。建议在自己本地编辑器里写上注释“prev2 永远是 i-2 的值prev1 永远是 i-1 的值”下次就不容易犯迷糊了。4.4 II 的拆分场景为什么不能在同一轮DP里加环形标记有些读者可能会想能不能在打家劫舍 I 的 DP 里加一个布尔标记表示“有没有偷第 0 间”在遍历到最后一间时再检查这个思路看起来合理但做起来很麻烦。因为线性 DP 的迭代方向是从左到右在走到最后一间之前DP 根本不知道前面到底有没有偷第 0 间滚动数组更是把历史信息丢弃了。你必须把一个额外的状态维度加进去变成 dp[i][state_of_first]这实际上等于把问题拆成了两个DP。与其在理解上绕弯子不如直接老实用两次线性DP。4.5 经典问题速查表问题特征处理方式复杂度线性数组不能相邻一维DPdp[i] max(dp[i-1], dp[i-2]nums[i])O(n)环形数组首尾相邻分类讨论去掉首或去掉尾分别做线性DP取maxO(n)二叉树上不能相邻树形DP后序遍历维护偷/不偷两个状态O(n)金额可能为0无需特殊处理DP天然兼容O(n)n1直接返回nums[0]避免rob_range退化O(1)5. 实测与对比同一道题四种写法的差异5.1 用一组数据实测我选了一个经典手写用例来演示输出过程nums [2, 3, 2, 3, 2, 3]。手动推演一下线性打劫不偷第0间考虑范围 [1, 5]即 [3, 2, 3, 2, 3]最大能偷的是 3 3 3 9线性打劫不偷最后一间考虑范围 [0, 4]即 [2, 3, 2, 3, 2]最大能偷的是 2 2 2 6 或 3 3 6结果 6正确答案为 max(9, 6) 9。这个例子特别有意思的地方在于两种拆法的结果差得很大说明“到底舍弃哪一间”对结果影响显著——你不能粗暴地固定舍弃某一端必须两种都算。这也是为什么拆分成两种情况的解法是必要的而不是随便去掉一端就行。5.2 性能对比实录我在本地用一个长度为 10000 的随机数组分别跑了四种写法递归枚举n30就放弃了指数爆炸标准DP约 2ms滚动数组DP约 1.2ms环形拆分滚动数组约 2.5ms滚动数组比标准DP快的原因主要是缓存友好、内存分配少环形拆分多了一次线性扫描所以时间约为两次滚动数组之和。但无论如何从 n10000 的量级看这都是在微秒毫秒级别的差距实际应用中不会被感知。真正拉开差距的是递归枚举和DP之间的指数与线性之别——这才是需要向面试官讲明白的核心。5.3 内存占用对比标准DP需要一个长度为 n1 的数组n10000 时约 80KB假设整数用 8 字节。滚动数组只用三个变量几乎可以忽略不记。对于打家劫舍这类小规模题目来说O(n) 空间其实也没啥压力但滚动数组作为一项通用技能在接龙式DP、股票买卖系列、编辑距离等问题里会反复用到值得一次掌握。6. 从打家劫舍看动态规划的通用方法论6.1 动态规划的五个关键步骤打家劫舍 I 和 II 虽然简单但它们完整地展示了DP题的标准解题流水线。我把这套流水线固定下来之后遇到任何新DP题都可以照着走定义状态要清楚 dp[i] 代表什么下标是“前 i 个”还是“第 i 个”这一含糊后面全乱写出状态转移方程这一步是核心本质是“分类讨论当前这一步的所有可能选择”确定初始化和边界长度 0、1、2 这些特殊情况要单独想清楚确定遍历顺序线性DP自左向右区间DP先短后长树形DP后序遍历确定返回值是 dp[n] 还是 max(dp) 还是 max(dp[i][0], dp[i][1])根据状态定义来我见过太多人拿到题就写代码结果卡在状态定义上半小时。其实花几分钟先把 dp[i] 说什么写清楚后面代码基本是顺水推舟的事。6.2 状态定义的几种常见套路打家劫舍 I 的状态定义有两种等价写法dp[i] 表示“第 i 间为止”和“前 i 间”。这两种写法本质一样但思考习惯不同。有些人习惯前一种有些人习惯后一种没有绝对优劣但关键是遍历时的下标、初始化、返回值三者必须和状态定义保持一致。我见过不少代码混用dp[i] 定义为“前 i 间”初始化却用了 dp[0] nums[0]遍历又从 i1 开始。这种混合写法bug率接近百分之百但肉眼很难看出来。所以我的建议是把状态定义写在注释第一行每次写转移方程前先看一眼注释三处一致了再动手。6.3 为什么不能直接贪心我遇到过很多人问这题能不能贪心每次选最大金额的房子偷然后跳过邻居不就行了吗答案是不行。贪心的局部最优不等于全局最优。举个反例nums [2, 5, 3, 5, 2]。贪心可能先挑 5下标1然后跳过下标0和2再从剩下的下标3和4里挑 5总和 10。但正确方案是 2 3 2 7不对让我重新算一下正确方案是偷下标0、2、4 2327或者偷下标1、3 5510。哦这个例子里贪心恰好是对的换一个nums [2, 4, 3, 5, 1]贪心先挑 5下标3跳过2和4剩下下标0、1可以偷但相邻只能选较大的4总和9。但最优是偷下标0、2、4 2316或者1、3 459。也不行。再换nums [3, 10, 6, 10, 3]贪心可能做比较选10跳过左右再选另一个10总和20最优确实是偷两个10 20。看起来要构造反例需要更精心的设计。其实最经典的反例是这个nums [2, 3, 2]。贪心如果先选3跳过两边的2得到3但最优其实也是3选22等于4等等2和2不相邻是首尾不相邻吗在线性版中下标0和2不相邻所以可以同时选最优是4。所以如果贪心先选了3得到3结果不是最优4。这个例子简洁明了。实际上最优是偷下标0和2总和4只偷下标1是3所以贪心会输。这正好说明贪心失效。我保留经典反例 [2, 3, 2]贪心选3最优却是4两头都偷。这样就直观证明了贪心不成立。那区间DP呢打家劫舍I有个区间版本问偷某个连续区间内的最大金额可以用同样的转移方程只是要先跑一遍前缀和来快速计算某个区间的总金额但注意偷窃不是全选所以区间版本其实不常用这个写法。打家劫舍II的rob_range其实就是区间DP的雏形只不过区间长度固定在整个数组规模。从方法论角度贪心为什么在这里不适用贪心选择“当前最大值”并不能保证后续选择空间最优。因为一旦选了某个高价值位置两侧都会封死这个“代价”可能比收益更大。DP之所以能胜出是因为它把“选择空间被压缩后的剩余最优”全部算了出来而不是只看眼前。6.4 从滚动数组到空间优化的通用技巧空间优化的判断标准只有一个状态转移方程中 dp[i] 只依赖前面固定个数的状态。依赖前1个用1个变量滚动依赖前2个用2个变量滚动依赖前m个用环形数组长度m滚动做一个通用模板# 假设 dp[i] 依赖 dp[i-1] 和 dp[i-2] prev2 初始值0 prev1 初始值1 for i in range(2, n1): cur f(prev1, prev2) # 按题意计算 prev2, prev1 prev1, cur这套模板在股票买卖最多一笔交易、斐波那契、爬楼梯、编辑距离依赖三个方向但可压缩为两行等题目中反复出现。建议最好自己动手推一遍编辑距离的空间压缩能彻底理解“为什么被覆盖的旧值要先保存”这个核心问题。7. 关于打家劫舍的几条实战心得与建议7.1 我建议的刷题顺序如果你是第一次接触动态规划我的建议顺序是这样的爬楼梯斐波那契数列打家劫舍 I打家劫舍 II打家劫舍 III树形DP可稍后前三步是为了熟悉 dp 数组的基本形态和转移写法第四步引入环形数组的拆分思维第五步则需要切换到树形DP。这套顺序是平滑的每一步的增量不会大到让人崩溃。7.2 面试中的表达技巧打家劫舍是一道高频面试题。我建议你在面试里不要只报答案而是按这个顺序讲先确认输入规模和边界n是多少金额是否非负说明为什么贪心不成立给一个反例定义状态解释 dp[i] 到底是什么写出转移方程并说明两个分支的含义再说边界条件和返回值最后补复杂度分析并顺手改成滚动数组版本这套表达方式其实展示的不是“你会做这道题”而是“你具备从问题到解法的完整思维链路”——这往往比单纯AC更有说服力。不少面试官在听完这套链路后会追问一个变体如果是环形数组呢这就正好切换到打家劫舍 II你顺势把分类讨论的思路讲出来即可。7.3 从刷题到真实场景的迁移很多人问打家劫舍这种题到底有什么实际用我觉得要诚实地说现实中你不会真的去规划偷窃路线这也不应该但“在互斥约束下做最优选择”这类模型应用范围极广不连续工作日的最优排班不能连续上两天夜班会议室预约选择相邻时间段不能都占用投资组合中“相邻标的不能同时重仓”的风控约束磁盘块分配中避免相邻物理块同时占用减少寻道时间把“房子”换成“资源”“相邻不能偷”换成“存在互斥关系”你会发现同样的DP骨架子在很多场景里都能套用。这正是学习经典题型的价值你练的不是题是建模能力。7.4 最后再分享一个小技巧刷题时千万不要只满足于“AC了”。每做完一道DP题我建议强迫自己回答三个问题如果把数组长度从 n 变成 2n我的解法还成立吗如果输入变成二维矩阵状态定义需要怎么扩展如果约束从“不能相邻”变成“不能连续三个”代码要改几行打家劫舍 I 的第三问尤其有意思只需把状态定义改成 dp[i] max(偷当前i且前一个不偷, 偷当前i且前一个偷但再前一个不偷, 不偷当前i)转移方程一下子多了一个维度但思路一脉相承。我自己就是在回答完这三个问题之后才真正对DP“开窍”的。所以别看打家劫舍是个入门题它值得你花一个下午的时间把它吃透。把这一题嚼烂动态规划的半壁江山就拿下了。