企业官网建设流程全解析

打家劫舍这道题，是我在刷 LeetCode Hot100 时遇到的第 68 道题，也是刷题群里被问到最多的高频动态规划题。题目描述非常简单——一条街上每户人家有一定金额，相邻两家不能被同时偷，否则会触发警报，问你能偷到的最大金额是多少。但真动手写的时候你会发现：状态怎么定义、边界条件怎么处理、要不要滚动数组优化，每一步都能展开讲出一堆细节。把它放在 Hot100 动态规划板块的前几道，就是因为它用最简单的外壳，把动态规划的核心套路完整演示了一遍。

这篇文章我不会只贴一个 AC 代码就完事，而是会从一个实际刷题人的视角，从初版思路聊到空间优化，再把我自己反复踩过的几个边界坑列清楚。如果你正在动态规划入门阶段，或者准备面试复盘高频题，那你来对地方了。代码我给出 Python 和 Java 两个版本，其它语言的写法逻辑完全一致，对着改就行。

1. 题面解读与解题方向判断

1.1 一条街上的抢劫问题到底在描述什么

原题给了一个非负整数数组nums，nums[i]表示第 i 户人家里的现金金额。要求不能偷相邻的两家，求能偷到的最大金额。比如：

• nums = [1,2,3,1]，最优方案是偷第 0 家和第 2 家，得到1 + 3 = 4。
• nums = [2,7,9,3,1]，最优方案是偷第 0、2、4 家，得到2 + 9 + 1 = 12。

第一个例子还算直观，第二个例子就有意思了。很多人第一反应是“隔一家偷一家”，那从 2 开始隔一个偷 9 再隔一个偷 1，得到 12，确实是正确答案。但要注意，隔一家偷一家并不是唯一的合法选择。你可以只偷第 1 家和第 3 家，拿到7 + 3 = 10；也可以偷第 1 家和第 4 家，拿到7 + 1 = 8；甚至可以偷第 0 家和第 3 家，拿到2 + 3 = 5。最终哪个方案收益最大，不能靠肉眼硬看，而是要靠一套规则把所有合法组合的收益比较清楚。

这个例子说明了一个关键点：不能把规则简化成“奇偶位分别求和再取最大”。我用一个反例说明为什么这样会错：[2,1,1,2]，奇数位和是2 + 1 = 3，偶数位和是1 + 2 = 3，但最优解其实是2 + 2 = 4，也就是偷第 0 家和第 3 家，它们的下标一个是奇数一个是偶数，跨越了奇偶分组。所以真正要找的，是所有满足“相邻不同偷”约束的合法组合里收益最大的那个。

1.2 为什么第一时间想到动态规划而不是贪心

有些同学会尝试用贪心：先选单户价值最高的那家，然后跳过相邻再选下一家。但这种“局部最优”的思路很容易翻车。[2,7,9,3,1]里单户价值最高的是第 1 家的 7，如果先选了它，第 0 家和第 2 家都会被跳过，剩下只能在 3 和 1 里再挑一个，总收益最大只有7 + 3 = 10，反而错过了2 + 9 + 1 = 12这个全局最优解。

动态规划和贪心的本质区别就在这里：贪心只关心当前这一步怎么选最划算，不回头评估这个选择对后续步骤的影响；而动态规划会把每一步的最优结果都保存下来，通过递推关系综合考虑“当前选不选”对未来收益的影响。对于这种“每步决策互相影响”的问题，决策阶段选对了问题模型，后面实现起来才有清晰的抓手。

1.3 无后效性：为什么当前状态只需要记住最优收益

动态规划能成立的前提叫无后效性。放在这道题里就是：当我们站在第 i 家门前时，前面怎么偷的细节完全不重要，重要的是从前 0 家到第 i-1 家已经能达到的最大收益是多少。因为第 i 家的决策只受第 i-1 家是否被偷影响，而“第 i-1 家是否被偷”这个信息，已经被压缩到前 i-1 家的最优收益以及一个额外状态里了。

这个“压缩历史”的思想是理解动态规划的关键。后面马上要讲的状态定义，就是围绕“站在当前房子时，我们只需要知道前两家范围内的最优收益”这一点展开的。想通了这一点，就不容易被一堆花里胡哨的推导搞晕。

2. 状态设计与递推关系的完整推导

2.1 用 dp[i] 表示前 i 家的最优解

先把索引约定好。nums[0..n-1]，定义dp[i]表示从第 0 家一直考虑到第 i 家时，能偷到的最大金额。注意这里的区间是闭区间，也就是说dp[i]已经覆盖了第 0 家到第 i 家的所有房屋。最终答案就是dp[n-1]。

初始化是新手最容易出错的地方。当只有一家时，dp[0] = nums[0]，因为没得选。当有两家时，dp[1] = max(nums[0], nums[1])，因为两家相邻不能同时偷，只能二选一。如果数组长度为 1，直接返回nums[0]，否则访问dp[1]就会数组越界，后面我会专门讲这个边界问题。

从第 2 家开始，也就是i >= 2时，站在第 i 家门前，当前只有两种决策：

1. 偷第 i 家，那么第 i-1 家必须放弃，收益来自前 i-2 家的最优值加上nums[i]。
2. 不偷第 i 家，收益就是前 i-1 家的最优值。

于是递推公式就是：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。

2.2 核心递推公式：偷还是不偷，这是一个收益问题

刚才说的两条分支，分别对应两个来源：

dp[i-2] + nums[i]代表“偷当前家”。因为相邻限制，前一家不能偷，所以要在前 i-2 家的最优基础上加上当前家的钱。

dp[i-1]代表“不偷当前家”。前 i-1 家怎么偷的都算好了，我直接继承这个结果就行。

为什么这里不用考虑“当前不偷但前 i-1 家没偷满”的情况？因为dp[i-1]本身就是前 i-1 家的最优值，无论它是否偷了第 i-1 家，对第 i 家的决策都没有影响。第 i 家不偷时，就是完全继承dp[i-1]；第 i 家要偷时，就是强制跳过第 i-1 家。两条路径覆盖了所有合法情况，取最大值就是当前这个位置的最优解。

用[1,2,3,1]手动推一遍，感受会很直观：

• dp[0] = 1
• dp[1] = max(1, 2) = 2
• dp[2] = max(dp[1], dp[0] + 3) = max(2, 1+3) = 4
• dp[3] = max(dp[2], dp[1] + 1) = max(4, 2+1) = 4

最终答案是 4，正确。整个过程中每个dp[i]都只依赖前两个状态，这也是后面空间优化能成立的根基。

2.3 二维状态版本：另一种值得知道的推导角度

如果觉得一维递推有点抽象，可以试试从二维状态入手。定义dp[i][0]表示第 i 家不偷时前 i 家的最大收益，dp[i][1]表示第 i 家偷时前 i 家的最大收益。转移规则直接对应题意：

• 第 i 家不偷，那第 i-1 家偷不偷都行：dp[i][0] = max(dp[i-1][0], dp[i-1][1])
• 第 i 家偷，那第 i-1 家必须不偷：dp[i][1] = dp[i-1][0] + nums[i]

答案取max(dp[n-1][0], dp[n-1][1])。

二维版本的好处是逻辑和题意一一对应，特别适合写进面试时的思路讲解。缺点是需要额外的空间存储两个状态值。但这不妨碍我们先用它把整个流程想清楚，然后再压缩成一维或滚动变量，反而更容易理解为什么压缩是安全的。

3. 三种可落地的实现方案与逐行讲解

3.1 方案 A：一维 DP 数组，最稳妥的写法

先写最直白的版本，空间复杂度 O(n)，但逻辑最清晰：

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]

对应 Java：

class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) return 0; if (n == 1) return nums[0]; int[] dp = new int[n]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]); } return dp[n-1]; } }

这个版本的重点在于dp[1]的初始化。为什么是max(nums[0], nums[1])而不是nums[1]？因为如果第一家金额比第二家大，比如[100, 1]，那最优解是偷第一家拿 100，而不是偷第二家拿 1。max在这里做了第一个真正的决策。循环从i = 2开始，是因为i = 0和i = 1已经单独初始化过了，从 2 开始才能安全地访问dp[i-2]。

3.2 方案 B：滚动数组，空间复杂度从 O(n) 压缩到 O(1)

因为递推只依赖dp[i-1]和dp[i-2]，我们只需要两个变量滚动更新就够了：

def rob(nums): prev2 = 0 # dp[i-2] prev1 = 0 # dp[i-1] for x in nums: cur = max(prev1, prev2 + x) prev2 = prev1 prev1 = cur return prev1

对应 Java：

class Solution { public int rob(int[] nums) { int prev2 = 0, prev1 = 0; for (int x : nums) { int cur = Math.max(prev1, prev2 + x); prev2 = prev1; prev1 = cur; } return prev1; } }

这里我相信很多刷题群的朋友会在变量更新顺序上卡壳。我特意强调一下：计算cur时用到了旧的prev1和prev2，所以必须先把prev2更新为旧的prev1，再把prev1更新为cur。如果顺序反了，prev2会先被覆盖成cur，下一次循环就再也拿不到真正的dp[i-2]，结果会莫名其妙地偏大。

有一种更稳的写法，用临时变量备份旧值：

def rob(nums): prev2 = 0 prev1 = 0 for x in nums: cur = max(prev1, prev2 + x) temp = prev1 prev1 = cur prev2 = temp return prev1

虽然多了一行，但思路不容易出错。个人建议，在面试这种精神高度紧张的环境下，写这种稳妥版本更好。

3.3 方案 C：二维状态写法，适合面试答题过渡

二维版本的实现也简单：

def rob(nums): n = len(nums) if n == 0: return 0 dp = [[0, 0] for _ in range(n)] dp[0][1] = nums[0] for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][1]) dp[i][1] = dp[i-1][0] + nums[i] return max(dp[n-1][0], dp[n-1][1])

这个方案的空间复杂度同样是 O(n)，从性能角度不算最优，但它能帮助理清“偷/不偷”两棵决策树。我在给同事讲动态规划入门时经常用它开头，等对方理解了再引导到滚动数组，效果比直接抛一维版要好很多。

三种方案对比如下：

表格里只有时间复杂度和空间复杂度的差异，核心递推思想完全一样。刷题时优先写方案 A，聊到空间优化再切换到方案 B，是面试里比较自然的节奏。

4. 容易出错的边界场景与排查实录

4.1 四个必测用例，覆盖全部边界

写代码之前先在心里跑一遍这几个用例，能在提交时省下不少时间：

我个人刷题的习惯是，每写完一版代码，先把这些用例在草稿纸上手算一遍，再提交 OJ。手算的价值在于帮助确认 dp 数组填得对不对，而不是单纯为了跑对答案。

4.2 我实操过程中踩过的三个坑

坑一：数组长度为 1 时访问dp[1]越界。很多初学者初始化dp后直接写dp[1] = max(nums[0], nums[1])，没有处理n == 1的情况，提交时nums[1]直接数组越界。正确做法是先检查长度，长度为 1 时直接返回nums[0]。

坑二：滚动数组更新顺序写反。前面提到过，如果先更新prev1再更新prev2，旧的历史状态会被覆盖丢失。我用一个临时变量备份prev1之后，基本再也没犯过这个错误。

坑三：把问题理解成“隔一家偷一家”，从而分成奇偶位求和取最大。[2,1,1,2]是很好的反例。奇偶位求和分别为 3 和 3，但最优解是偷第 0 和第 3 家得到 4。为什么奇偶法在这里失效？因为最优解不一定是等间隔的，它可能是先跳两家再跳一家，组合必须靠动态规划来枚举，而不是靠固定步长。

4.3 面试追问：空间优化一定比 DP 数组更优吗

很多刷题指南会直接告诉你空间优化是“必须的”，但从实际工程和面试角度看，不一定。

如果你只需要返回最终答案，滚动变量确实更好。但如果面试官追问“能不能输出偷了哪几家”，这时滚动变量就没法做了，因为你在空间压缩时丢弃了所有历史状态。要还原路径，你需要完整的dp数组，然后从dp[n-1]往前回溯：如果dp[i]等于dp[i-1]，说明第 i 家没偷，跳到 i-1；如果等于dp[i-2] + nums[i]，说明第 i 家偷了，记录它然后跳到 i-2。

这个回溯过程在面试里很加分，因为它说明了“空间压缩是有代价的”。我通常会先说清楚：追求 O(1) 空间是刷题最优解，但强调历史状态可回溯是在展示工程思维。这两种表达不冲突，能体现你对时间、空间、可维护性的综合权衡。

5. 从打家劫舍延伸出去的变体与进阶题目

5.1 打家劫舍 II：房子变成环形

LeetCode 上紧接着的进阶题是 213 打家劫舍 II，房子首尾相连成一个环形。由于第一家和最后一家现在也是相邻的，不能同时偷，所以问题变成两个互不影响的线性子问题：

• 不偷第一家，考虑nums[1:]
• 不偷最后一家，考虑nums[:-1]

分别用打家劫舍 I 的解法跑一遍，取最大值即可。为什么这样可以？因为环形约束只在首尾两家之间生效，我们通过“排除其中一个端点”把环断开成线，这样线性解法直接可用。实现时通常写一个辅助函数robRange(nums, l, r)，内部用滚动数组处理[l, r)区间，比单独面对整个数组更容易管理边界。

有一点要注意：当n == 1时，nums[1:]和nums[:-1]都会变成空数组，直接取nums[0]返回是更简洁的处理方式。如果硬套子问题，容易在区间边界上绕晕。

5.2 打家劫舍 III：树形 DP 登场

如果把房子排列成二叉树，父节点和子节点不能同时偷，就变成 337 打家劫舍 III。线性 dp 在这里失效，因为状态不是按数组下标推进，而是沿着树的节点递归。这时要用树形 DP 的思想：对每个节点返回两个状态值，分别表示“偷该节点”和“不偷该节点”时，该子树能获得的最大收益。

核心代码大概长这样：

def rob(root): def dfs(node): if not node: return [0, 0] left = dfs(node.left) right = dfs(node.right) # 偷当前节点，子节点都不能偷 rob_cur = node.val + left[0] + right[0] # 不偷当前节点，子节点偷或不偷取最大 not_rob_cur = max(left) + max(right) return [not_rob_cur, rob_cur] return max(dfs(root))

这个变体本质上还是“当前节点偷不偷”的决策，只是把“相邻”的概念从数组下标变成了树上的父子关系。做完 198 和 213 之后再回头看 337，会觉得思路是连贯的。

5.3 与最大子数组和、背包问题的横向对比

刷题时间长了会发现，LeetCode 热门 100 题里的动态规划其实是成体系的。70 爬楼梯讲线性递推；198 打家劫舍讲带约束的线性递推；53 最大子数组和讲另一种线性状态设计；322 零钱兑换则引入了背包的“物品无限/物品有限”思想。这些题目放在一起复习，收益比单刷一道题大很多。

打家劫舍本质上可以理解为“带相邻冲突约束的加权选择问题”，背包问题则是“带容量约束的选或不选问题”。两种问题在状态设计上有天然的相似性，都是考察“每个物品选还是放弃”对全局最优的影响。理解了这个底层逻辑，遇到新的变体就不会慌了，因为核心问题永远是三个：状态是什么、转移怎么写、边界怎么定。

5.4 推荐的 Hot100 动态规划刷题顺序

最后给一个我实测下来比较顺的动规刷题顺序：

从简单到复杂，从线性到树形，再到背包，每一步都建立在前面题目的基础上。把这一串刷明白，Hot100 里大部分动态规划题你都会觉得似曾相识。

最后分享一个我自己一直保留的习惯：刷动态规划题，我从来不会只写代码，而是在草稿纸上把 dp 数组从前往后手动填一遍。比如[2,7,9,3,1]这个用例，手推dp[0]=2，dp[1]=max(2,7)=7，dp[2]=max(7,2+9)=11，dp[3]=max(11,7+3)=11，dp[4]=max(11,11+1)=12。填完之后自然就明白滚动数组在干什么，面试时讲起状态转移也会顺很多。这个习惯我延续到了几乎所有动态规划题上，确实帮我少走了不少弯路。