从打家劫舍问题深解动态规划：贪心与DP的博弈及进阶应用

在动态规划的入门练习中，“打家劫舍”问题是继“爬楼梯”之后，最具代表性的经典题目之一。它不仅延续了动态规划“大问题拆解为小问题、记忆化存储避免重复计算”的核心思想，更增加了“选择与取舍”的决策维度——不同于爬楼梯的线性递推，打家劫舍需要在“偷当前房屋”和“不偷当前房屋”之间做出选择，最终求得最大收益。这种决策逻辑，正是动态规划解决多选择最优解问题的核心精髓。

很多新手在接触这道题时，容易陷入两个误区：一是试图用贪心算法求解，误以为“每次偷最大金额的房屋”就能得到最优解，却忽略了贪心算法的短视性；二是能写出基础的动态规划代码，却无法理解状态定义的本质，更谈不上优化空间复杂度、应对变种题目。本文将以打家劫舍问题为核心，从题目本身出发，逐步拆解解题思路，对比贪心与DP的差异，讲解基础解法、空间优化、极致优化，再延伸到各类变种题目，深入探讨题目背后的算法逻辑，带你从“会做这道题”到“理解这类题”，再到“能举一反三解决复杂变种”。

全文篇幅超3000字，结构清晰、逻辑连贯，兼顾新手入门的易懂性和进阶学习的深度，无论是刚接触动态规划的新手，还是想巩固DP思路的学习者，耐心读完，都能有所收获，对动态规划的“决策性”有更深刻的认知。

一、题目详解：打家劫舍问题的完整描述与核心考点

1.1 基础题目描述（LeetCode 198. 打家劫舍）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房屋内都藏有一定的现金，影响你偷窃的唯一制约因素就是：相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2) ，偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

示例 3：

输入：[0] 输出：0 解释：只有一间房屋，金额为0，偷窃到的最高金额为0。

示例 4：

输入：[2,1,1,2] 输出：4 解释：偷窃 1 号房屋 (金额 = 2) ，偷窃 4 号房屋 (金额 = 2)，总金额 4；或偷窃 2 号和 4 号（1+2=3）、1 号和 3 号（2+1=3），均小于4，因此最优解为4。

1.2 题目约束

明确题目约束，能帮助我们更好地判断解题思路的合理性，避免不必要的冗余思考，打家劫舍基础题的常见约束如下：

• 1 ≤ 房屋数量（数组长度）≤ 100（基础难度，适合新手练手）；
• 进阶约束：1 ≤ 房屋数量 ≤ 100000（需要优化空间复杂度，避免内存溢出）；
• 每个房屋的金额 ≥ 0（无负金额，无需考虑“放弃高金额房屋以避免负收益”的情况）；
• 核心约束：不能偷窃相邻房屋，这是题目唯一的决策限制，也是解题的关键。

1.3 核心考点

这道题的核心考点并非“计算最高金额”，而是通过题目理解动态规划解决“多选择最优解”的逻辑，具体考点包括：

1. 如何拆解问题：将“偷窃前n间房屋的最高金额”这个大问题，拆解为“偷第n间房屋”和“不偷第n间房屋”两个小问题；
2. 如何定义状态：明确dp[i]的含义（即“偷窃前i间房屋的最高金额”），理解状态的“最优子结构”；
3. 如何推导状态转移方程：根据“偷与不偷”的决策，推导dp[i]与dp[i-1]、dp[i-2]之间的关系；
4. 如何确定边界条件：明确dp[0]、dp[1]的值，避免迭代或递归时出现逻辑错误；
5. 贪心算法的局限性：理解为什么贪心算法无法解决这道题，掌握“贪心vsDP”的适用场景差异；
6. 空间复杂度优化：从O(n)优化到O(1)，进一步理解“滚动数组”思想在DP优化中的应用；
7. 变种题目适配：将基础思路迁移到环形房屋、树形房屋等变种题目中，提升举一反三的能力。

很多人做这道题时，只会写基础的DP代码，却忽略了两个关键：一是状态定义的本质的是“前i间房屋的最优解”，而非“第i间房屋是否被偷”；二是贪心算法的误区，这恰恰是理解DP必要性的关键。吃透这道题，能帮助我们快速掌握“决策性DP”的核心逻辑，为后续解决更复杂的DP问题（如背包问题、编辑距离）打下基础。

二、常见误区：为什么贪心算法行不通？

在讲解动态规划解法之前，我们先重点分析一个新手最容易陷入的误区——用贪心算法求解。很多人看到“求最高金额”，第一反应就是“每次选择当前剩余房屋中金额最大的那间，然后跳过相邻房屋”，这种思路看似合理，实则存在严重的逻辑漏洞，因为贪心算法的“短视性”会导致我们错过全局最优解。

2.1 贪心算法的思路与尝试

贪心算法的核心思路：每次都做局部最优选择，期望通过局部最优积累得到全局最优。针对打家劫舍问题，贪心算法的具体操作如下：

1. 遍历房屋数组，找到当前金额最大的房屋，记录其金额和索引；
2. 将该房屋的金额加入总收益，同时标记该房屋及其相邻房屋为“已跳过”（无法再偷）；
3. 在剩余未标记的房屋中，重复步骤1和步骤2，直到所有房屋都被标记；
4. 返回总收益，认为这是最高金额。

我们用示例4来测试这个思路：输入[2,1,1,2]。

• 第一次遍历：最大金额为2（索引0或3），假设选择索引0，总收益=2，标记索引0和1（相邻房屋）；
• 剩余未标记房屋：索引2（金额1）、索引3（金额2）；
• 第二次遍历：剩余房屋中最大金额为2（索引3），总收益=2+2=4，标记索引3和2（相邻房屋）；
• 所有房屋标记完毕，总收益为4，与正确答案一致。

看似这个思路可行，但我们再用一个反例来验证：输入[3,2,7,10]。

按照贪心算法的思路：

• 第一次遍历：最大金额为10（索引3），总收益=10，标记索引3和2；
• 剩余未标记房屋：索引0（3）、索引1（2）；
• 第二次遍历：最大金额为3（索引0），总收益=10+3=13，标记索引0和1；
• 总收益为13。

但实际上，最优解是偷窃索引0（3）和索引3（10）吗？不！再仔细看：偷窃索引0（3）和索引2（7），总金额为3+7=10，比13小；偷窃索引1（2）和索引3（10），总金额为12，也比13小；哦？这个反例似乎不成立？那我们换一个更经典的反例：输入[5,5,10,100,10,5]。

贪心算法思路：

• 第一次遍历：最大金额为100（索引3），总收益=100，标记索引2、3、4；
• 剩余未标记房屋：索引0（5）、索引1（5）、索引5（5）；
• 第二次遍历：最大金额为5（索引0、1、5均可），选择索引0，总收益=105，标记索引0、1；
• 剩余未标记房屋：索引5（5），标记索引5，总收益=105+5=110；

但全局最优解是什么？偷窃索引0（5）、索引3（100）、索引5（5）？不，索引0和1相邻，索引3和2、4相邻，索引5和4相邻，所以索引0、3、5可以同时偷，总金额=5+100+5=110，和贪心结果一致？那再换一个反例：输入[2,7,9,3,1,10]。

贪心算法思路：

• 第一次遍历：最大金额为10（索引5），总收益=10，标记索引4、5；
• 剩余未标记房屋：索引0（2）、1（7）、2（9）、3（3）；
• 第二次遍历：最大金额为9（索引2），总收益=10+9=19，标记索引1、2、3；
• 剩余未标记房屋：索引0（2），总收益=19+2=21；

而全局最优解是：偷窃索引0（2）、索引2（9）、索引5（10），总金额=2+9+10=21，还是和贪心结果一致？难道贪心算法真的可行？

别急，我们再看一个关键反例：输入[3, 1, 3, 100]。

贪心算法思路：

• 第一次遍历：最大金额为100（索引3），总收益=100，标记索引2、3；
• 剩余未标记房屋：索引0（3）、索引1（1）；
• 第二次遍历：最大金额为3（索引0），总收益=100+3=103；

但全局最优解是：偷窃索引0（3）和索引3（100）？不，索引0和1相邻，索引3和2相邻，0和3不相邻，所以总金额3+100=103，还是一致？那到底有没有反例？

当然有！关键反例：输入[1,3,1,3,100]。

贪心算法思路：

• 第一次遍历：最大金额为100（索引4），总收益=100，标记索引3、4；
• 剩余未标记房屋：索引0（1）、1（3）、2（1）；
• 第二次遍历：最大金额为3（索引1），总收益=100+3=103，标记索引0、1、2；
• 最终总收益=103。

而全局最优解是：偷窃索引1（3）和索引4（100）吗？不！再仔细看：偷窃索引0（1）、索引2（1）、索引4（100）？不行，索引0和1相邻，索引2和1、3相邻，索引4和3相邻，0和2不相邻，2和4不相邻，所以1+1+100=102，比103小；哦？不对，再想：偷窃索引1（3）和索引4（100）是103，偷窃索引3（3）和索引4（100）不行（相邻），偷窃索引0（1）和索引3（3）和索引4（100）不行（3和4相邻）。那这个反例也不成立？

别急，我们换一个更极端的反例：输入[5,1,1,5]。

贪心算法思路：

• 第一次遍历：最大金额为5（索引0或3），选择索引0，总收益=5，标记索引0、1；
• 剩余未标记房屋：索引2（1）、索引3（5）；
• 第二次遍历：最大金额为5（索引3），总收益=5+5=10，标记索引2、3；
• 最终总收益=10，这是全局最优解。

2.2 贪心算法的本质漏洞：为什么看似可行，实则不通用？

看到这里，很多人会疑惑：为什么我找了这么多例子，贪心算法都能得到正确结果？难道这道题可以用贪心算法求解？

答案是：基础版打家劫舍问题，部分贪心思路可能得到正确结果，但这只是巧合，贪心算法并不具备通用性，无法应对所有情况。其核心漏洞在于：贪心算法只关注“当前局部最优”，而忽略了“当前选择对后续选择的影响”，可能导致后续无法选择更高金额的房屋，从而错过全局最优解。

我们举一个真正能打破贪心算法的反例：输入[4,1,2,7,5,3,1]。

先看贪心算法的执行过程：

1. 第一次遍历：最大金额为7（索引3），总收益=7，标记索引2、3、4；
2. 剩余未标记房屋：索引0（4）、1（1）、5（3）、6（1）；
3. 第二次遍历：最大金额为4（索引0），总收益=7+4=11，标记索引0、1；
4. 剩余未标记房屋：索引5（3）、6（1）；
5. 第三次遍历：最大金额为3（索引5），总收益=11+3=14，标记索引4、5、6；
6. 最终总收益=14。

再看全局最优解：偷窃索引0（4）、索引3（7）、索引5（3），总金额=4+7+3=14？不对，还有更优的选择：偷窃索引0（4）、索引3（7）、索引6（1），总金额=4+7+1=12；或者偷窃索引1（1）、索引3（7）、索引5（3），总金额=11；或者偷窃索引0（4）、索引4（5）、索引6（1），总金额=10；哦？似乎贪心结果还是最优？

这里我们需要明确一个关键：基础版打家劫舍问题（线性房屋、无环、无树形结构），贪心算法“每次选最大金额房屋并跳过相邻”，在某些情况下确实能得到最优解，但这并非算法的通用性，而是题目场景的特殊性导致的。而当题目变为“环形房屋”“树形房屋”“房屋有冷却时间”等变种时，贪心算法会立刻失效。

比如“环形房屋”问题（所有房屋围成一圈，第一间和最后一间相邻）：输入[2,3,2]。贪心算法会选择索引1（3），总收益3；而全局最优解是选择索引0（2）或索引2（2），总收益2，看似贪心结果更优？不对，再看输入[1,2,3,1]（环形）：贪心算法选择索引2（3），总收益3；而全局最优解是选择索引1（2）和索引3（1），总收益3，还是一致？再看输入[5,3,4,11,2]（环形）：贪心算法选择索引3（11），总收益11；全局最优解是选择索引0（5）和索引3（11），但环形结构中0和4相邻，3和2、4相邻，0和3不相邻，所以5+11=16，这才是全局最优解！而贪心算法只选了11，错过了5，导致结果错误。

这就是贪心算法的致命缺陷：它无法处理“全局决策关联”的场景，只能看到当前的局部最优，而动态规划通过“状态存储”，记录了前i个元素的最优解，从而实现了全局最优决策。因此，即使基础版打家劫舍问题贪心算法可能“蒙对”，但我们仍然需要用动态规划来求解，这不仅是为了掌握正确的算法思路，更是为了应对后续的变种题目。

三、解题思路拆解：从暴力递归到动态规划的进化之路

和爬楼梯问题一样，学习打家劫舍的动态规划解法，最好的方式是从“暴力递归”入手，感受暴力解法的弊端，然后逐步优化，最终过渡到标准DP、空间优化、极致优化，这样既能理解动态规划的必要性，也能清晰掌握每一步优化的逻辑，避免死记硬背代码。

3.1 暴力递归解法：最直观但效率最低的思路

3.1.1 思路分析

我们先回归题目本质，拆解问题：要计算偷窃前n间房屋的最高金额，对于第n间房屋（索引为i），我们只有两种选择：偷，或者不偷。

1. 选择偷第i间房屋：那么根据题目约束，我们不能偷第i-1间房屋，此时偷窃前i间房屋的最高金额 = 偷窃前i-2间房屋的最高金额 + 第i间房屋的金额；
2. 选择不偷第i间房屋：那么我们可以偷第i-1间房屋，此时偷窃前i间房屋的最高金额 = 偷窃前i-1间房屋的最高金额；

因此，偷窃前i间房屋的最高金额，就是这两种选择的最大值。这个逻辑可以用递归公式表示为：

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

接下来，我们需要确定递归的终止条件（边界条件）：

• 当i = 0（只有第1间房屋）：只能偷这一间，所以f(0) = nums[0]；
• 当i = 1（有两间房屋）：选择金额较大的一间偷，所以f(1) = max(nums[0], nums[1])；

这里需要注意：递归的参数i表示“房屋索引”，从0开始，对应前i+1间房屋。根据这个逻辑，我们可以直接写出暴力递归的代码。

3.1.2 暴力递归代码（Python）

def rob(nums): # 递归函数：返回偷窃前i+1间房屋（索引0到i）的最高金额 def dfs(i): # 边界条件1：只有一间房屋（索引0） if i == 0: return nums[0] # 边界条件2：有两间房屋（索引0和1） if i == 1: return max(nums[0], nums[1]) # 递归调用：偷第i间 或 不偷第i间，取最大值 return max(dfs(i-1), dfs(i-2) + nums[i]) # 处理特殊情况：数组为空 if not nums: return 0 # 调用递归函数，传入最后一间房屋的索引 return dfs(len(nums)-1)

3.1.3 暴力递归的弊端：重复计算与时间复杂度分析

和爬楼梯的暴力递归一样，这个代码看似简单，却存在大量重复计算的问题。我们以nums = [2,7,9,3,1]（索引0-4）为例，画出递归调用树，就能清晰看到问题所在：

f(4) = max( f(3), f(2) + 1 )

f(3) = max( f(2), f(1) + 3 ) （这里的f(2)需要计算）

f(2) = max( f(1), f(0) + 9 ) （这里的f(1)、f(0)需要计算）

f(1) = max(2,7) =7 （重复计算多次）

f(0) =2 （重复计算多次）

f(2) = max(7, 2+9)=11 （和上面的f(2)重复，需要重新计算）

从调用树可以看出，计算f(4)需要f(3)和f(2)，计算f(3)又需要f(2)和f(1)，f(2)被计算了两次；当数组长度增大时，重复计算的次数会呈指数级增长。比如数组长度为10时，f(10)需要f(9)和f(8)，f(9)需要f(8)和f(7)，以此类推，重复计算的次数会多到难以想象。

我们来分析时间复杂度：假设计算f(i)需要的时间为T(i)，那么根据递归公式，T(i) = T(i-1) + T(i-2) + O(1)（O(1)是指每次递归调用的基础操作时间）。这个递归式和斐波那契数列的递推式一致，其时间复杂度是O(2ⁿ)，属于指数级时间复杂度。

指数级时间复杂度的弊端非常明显：当数组长度n=30时，计算次数大约是2³⁰ ≈ 10⁹次，普通计算机已经需要花费几秒时间；当n=40时，计算次数达到2⁴⁰ ≈ 10¹²次，计算机几乎无法在合理时间内完成；当n=100时，更是天文数字，完全无法计算。

此外，暴力递归还存在栈溢出的问题：Python的递归栈深度有限（默认约为1000），当数组长度超过1000时，递归调用会超出栈的最大深度，导致程序崩溃。

因此，暴力递归虽然直观，但完全不适合实际应用，我们必须对其进行优化，核心优化方向就是“避免重复计算”。

3.2 优化一：记忆化递归（自上而下的动态规划）

3.2.1 优化思路：避免重复计算，存储中间结果

暴力递归的核心问题是“重复计算”，那么优化思路就很明确——将已经计算过的f(i)的值存储起来，下次需要使用时直接调用，不需要重新计算。这种方法被称为“记忆化存储”，对应的递归方式称为“记忆化递归”，本质上是“自上而下”的动态规划。

具体来说，我们可以用一个数组（或字典）来存储已经计算过的f(i)的值，当递归调用到f(i)时，先检查数组中是否已经有这个值：

• 如果有，直接返回数组中的值，不需要重新计算；
• 如果没有，计算f(i)的值，并存入数组中，再返回结果。

这种方式从大问题f(n-1)（最后一间房屋的索引）出发，逐步拆解为小问题f(n-2)、f(n-3)，直到遇到边界条件f(0)、f(1)，然后将小问题的结果存储起来，逐步向上推导大问题的结果。因为每个小问题只计算一次，所以效率会极大提升。

3.2.2 记忆化递归代码（Python）

我们可以用两种方式实现记忆化存储：一种是使用数组存储（手动记忆化），另一种是使用装饰器（如lru_cache），这里我们分别给出代码，方便大家理解。

方式一：使用数组存储（手动记忆化）

def rob(nums): if not nums: return 0 n = len(nums) # 初始化记忆数组，memo[i]表示偷窃前i+1间房屋（索引0到i）的最高金额 memo = [0] * n # 递归函数，带记忆化存储 def dfs(i): if i == 0: memo[i] = nums[0] return memo[i] if i == 1: memo[i] = max(nums[0], nums[1]) return memo[i] # 如果已经计算过，直接返回 if memo[i] != 0: return memo[i] # 否则计算memo[i]，并存储 memo[i] = max(dfs(i-1), dfs(i-2) + nums[i]) return memo[i] return dfs(n-1)

方式二：使用lru_cache装饰器（自动记忆化）

from functools import lru_cache def rob(nums): if not nums: return 0 # 装饰器自动缓存递归调用结果 @lru_cache(maxsize=None) def dfs(i): if i == 0: return nums[0] if i == 1: return max(nums[0], nums[1]) return max(dfs(i-1), dfs(i-2) + nums[i]) return dfs(len(nums)-1)

这种方式非常简洁，Python的lru_cache装饰器会自动缓存递归调用的结果，避免重复计算，本质上和手动记忆化的思路一致。需要注意的是，装饰器只能用于可哈希的参数，这里的i是整数，符合要求。

3.2.3 记忆化递归的时间复杂度与空间复杂度

时间复杂度：因为每个小问题f(i)（i从0到n-1）只计算一次，每次计算的时间是O(1)，所以总时间复杂度是O(n)，相比暴力递归的O(2ⁿ)，效率提升了几个数量级。比如n=100时，暴力递归需要计算2¹⁰⁰次，而记忆化递归只需要计算100次，差距极其明显。

空间复杂度：主要分为两部分——递归栈的空间和记忆化存储的空间。

• 记忆化存储的空间：我们使用了一个大小为n的数组（或缓存），所以这部分空间是O(n)；
• 递归栈的空间：递归调用的深度是n（从f(n-1)调用到f(0)），所以这部分空间是O(n)；

因此，记忆化递归的总空间复杂度是O(n)。

虽然记忆化递归解决了重复计算的问题，效率大幅提升，但仍然存在递归栈溢出的问题——当数组长度超过1000时，递归深度会超出Python的默认栈深度，导致程序崩溃。为了解决这个问题，我们可以将“自上而下”的递归，改为“自下而上”的迭代，也就是标准的动态规划解法。

3.3 优化二：标准动态规划解法（自下而上的迭代）

3.3.1 思路分析：从边界条件出发，逐步推导大问题

标准的动态规划解法采用“自下而上”的思路：不再从大问题f(n-1)出发拆解小问题，而是从边界条件f(0)、f(1)出发，逐步计算出f(2)、f(3)、……、f(n-1)，直到得到最终结果。这种思路的核心仍然是动态规划的三大要素：状态定义、状态转移方程、边界条件，我们重新明确一下这三大要素，确保理解无误。

1. 状态定义：定义dp[i]为“偷窃前i+1间房屋（索引0到i）的最高金额”。这里需要注意，dp[i]的含义是“前i+1间房屋的最优解”，而不是“第i间房屋是否被偷”——很多新手容易误解这一点，误以为dp[i]需要记录“第i间房屋是否被偷”，但实际上，我们不需要关心具体哪间房屋被偷，只需要关心前i+1间房屋的最大收益，这就是状态的“最优子结构”。
2. 状态转移方程：根据“偷与不偷”的决策，推导dp[i]与dp[i-1]、dp[i-2]的关系： 因此，状态转移方程为：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
   1. 不偷第i间房屋：此时前i+1间房屋的最高金额 = 前i间房屋的最高金额，即dp[i] = dp[i-1]；
   2. 偷第i间房屋：此时不能偷第i-1间房屋，前i+1间房屋的最高金额 = 前i-1间房屋的最高金额 + 第i间房屋的金额，即dp[i] = dp[i-2] + nums[i]；
3. 边界条件：
   1. 当i=0（只有1间房屋）：dp[0] = nums[0]（只能偷这一间）；
   2. 当i=1（有2间房屋）：dp[1] = max(nums[0], nums[1])（选择金额较大的一间偷）；

这里我们可以举一个具体的例子，帮助大家理解计算过程：nums = [2,7,9,3,1]（n=5）。

• dp[0] = 2（只有第1间房屋，金额2）；
• dp[1] = max(2,7) =7（两间房屋，选金额7的）；
• dp[2] = max(dp[1], dp[0]+9) = max(7, 2+9)=11（不偷第3间，收益7；偷第3间，收益2+9=11，选11）；
• dp[3] = max(dp[2], dp[1]+3) = max(11,7+3)=11（不偷第4间，收益11；偷第4间，收益7+3=10，选11）；
• dp[4] = max(dp[3], dp[2]+1) = max(11,11+1)=12（不偷第5间，收益11；偷第5间，收益11+1=12，选12）；

最终结果dp[4] =12，和示例2的输出一致，证明思路正确。

3.3.2 标准动态规划代码（Python）

def rob(nums): # 处理特殊情况：数组为空 if not nums: return 0 n = len(nums) # 处理特殊情况：只有一间房屋 if n == 1: return nums[0] # 初始化dp数组，dp[i]表示偷窃前i+1间房屋的最高金额 dp = [0] * n # 边界条件 dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) # 自下而上迭代计算dp[2]到dp[n-1] for i in range(2, n): dp[i] = max(dp[i-1], dp[i-2] + nums[i]) # 返回最终结果：前n间房屋的最高金额 return dp[-1]

3.3.3 标准动态规划的时间复杂度与空间复杂度

时间复杂度：我们只需要进行一次循环，从2迭代到n-1，每次迭代的操作是O(1)（取最大值、加法），所以总时间复杂度是O(n)，和记忆化递归一致。

空间复杂度：我们使用了一个大小为n的dp数组，用于存储中间结果，所以空间复杂度是O(n)。

相比记忆化递归，标准动态规划的优势在于：避免了递归栈溢出的问题，因为迭代不需要调用栈，即使数组长度n=1e6，也能正常运行（只要内存足够）；同时，迭代的效率通常比递归更高，因为递归需要进行函数调用，存在一定的开销，而迭代是直接的循环操作，开销更小。

但标准动态规划仍然存在优化空间——我们发现，计算dp[i]时，只需要用到dp[i-1]和dp[i-2]这两个前序值，而不需要用到dp[0]到dp[i-3]的所有值。因此，我们可以不需要存储整个dp数组，只需要用两个变量存储前两个值，就能计算出当前值，从而将空间复杂度优化到O(1)。

3.4 优化三：空间复杂度优化（滚动数组思想）

3.4.1 优化思路：用变量替代数组，滚动更新

根据状态转移方程dp[i] = max(dp[i-1], dp[i-2] + nums[i])，我们可以发现一个关键规律：

• 计算dp[i]时，只需要知道dp[i-1]（前i间房屋的最高金额）和dp[i-2]（前i-1间房屋的最高金额）的值；
• 计算dp[i+1]时，只需要知道dp[i]（前i+1间房屋的最高金额）和dp[i-1]（前i间房屋的最高金额）的值；

因此，我们可以用两个变量来存储这两个前序值，不需要存储整个dp数组，具体如下：

• prev_prev：表示dp[i-2]，即前i-1间房屋的最高金额；
• prev：表示dp[i-1]，即前i间房屋的最高金额；

然后，当前值current = max(prev, prev_prev + nums[i])（即dp[i]）；计算完current后，我们再滚动更新两个变量的值：prev_prev = prev（将前i间房屋的最高金额，更新为前i-1间的），prev = current（将前i+1间房屋的最高金额，更新为当前的），这样就可以继续计算下一个值。

这种思路就是“滚动数组”思想——本质上是用有限的变量替代数组，模拟数组的滚动更新，从而节省空间。对于打家劫舍问题来说，滚动数组可以将空间复杂度从O(n)优化到O(1)，这是非常关键的优化，尤其是当数组长度极大时（如n=1e6），可以大幅节省内存，避免内存溢出。

3.4.2 滚动数组优化代码（Python）

def rob(nums): # 处理特殊情况：数组为空 if not nums: return 0 n = len(nums) # 处理特殊情况：只有一间房屋 if n == 1: return nums[0] # 初始化前两个值：prev_prev = dp[i-2], prev = dp[i-1] prev_prev = nums[0] # dp[0]，前1间房屋的最高金额 prev = max(nums[0], nums[1]) # dp[1]，前2间房屋的最高金额 # 迭代计算从i=2到i=n-1的值（前3间到前n间房屋） for i in range(2, n): # 当前值：前i+1间房屋的最高金额 current = max(prev, prev_prev + nums[i]) # 滚动更新：prev_prev变为原来的prev，prev变为当前的current prev_prev, prev = prev, current # 循环结束后，prev就是前n间房屋的最高金额（dp[n-1]） return prev

3.4.3 优化后的时间复杂度与空间复杂度

时间复杂度：仍然是O(n)，和标准动态规划一致，因为我们还是需要迭代n-2次（从2到n-1），每次迭代的操作是O(1)，没有增加额外的计算量。

空间复杂度：O(1)，因为我们只使用了三个变量（prev_prev、prev、current），无论数组长度n多大，变量的数量都是固定的，不会随着n的增大而增加内存占用。

这种优化后的解法，是基础版打家劫舍问题的最优解法——时间复杂度O(n)，空间复杂度O(1)，既高效又节省内存，即使n=1e6，也能在极短的时间内运行完成（Python中迭代1e6次只需要几毫秒）。

我们可以用示例2来验证这个代码：nums = [2,7,9,3,1]。

• prev_prev = 2（dp[0]），prev = max(2,7)=7（dp[1]）；
• i=2：current = max(7, 2+9)=11 → prev_prev=7，prev=11；
• i=3：current = max(11,7+3)=11 → prev_prev=11，prev=11；
• i=4：current = max(11,11+1)=12 → prev_prev=11，prev=12；
• 返回prev=12，正确。

3.5 优化四：极致优化（针对特殊场景）

对于基础版打家劫舍问题来说，滚动数组优化后的O(n)时间、O(1)空间解法已经足够应对所有场景，但我们可以针对一些特殊场景，做进一步的极致优化，虽然实际应用场景有限，但能帮助我们更深入理解算法的灵活性。

3.5.1 场景一：数组中存在大量0

如果数组中存在大量0（比如nums = [0,0,0,0,100]），此时我们可以跳过连续的0，直接计算非0元素的位置，因为偷0金额的房屋没有意义，不会增加总收益。这种优化可以减少迭代次数，但时间复杂度仍然是O(n)（最坏情况下没有0，和原代码一致），空间复杂度仍然是O(1)。

3.5.2 场景二：数组长度极小（n≤2）

我们已经在代码中处理了n=0和n=1的特殊情况，对于n=2，直接返回max(nums[0], nums[1])，不需要进入循环，这也是一种小优化，能提升代码的执行效率（虽然影响不大，但体现了代码的严谨性）。

3.5.3 极致优化代码（Python）

def rob(nums): n = len(nums) # 处理特殊情况：数组为空、只有1间、只有2间房屋 if n == 0: return 0 if n == 1: return nums[0] if n == 2: return max(nums[0], nums[1]) # 滚动数组优化，跳过连续0的优化（可选） prev_prev = nums[0] prev = max(nums[0], nums[1]) for i in range(2, n): # 跳过0金额房屋，直接继承前一个值 if nums[i] == 0: current = prev else: current = max(prev, prev_prev + nums[i]) prev_prev, prev = prev, current return prev

需要注意的是，这种极致优化只适用于特定场景，对于普通数组，性能提升不明显，因此在实际面试中，不需要刻意写这种优化，滚动数组的基础优化版本已经足够。

四、常见误区与注意事项

很多新手在做打家劫舍问题时，虽然能写出代码，但往往存在一些细节误区，导致代码出错或效率低下，尤其是在状态定义、边界条件和变种题目适配方面。这里我们总结了几个常见误区，帮助大家避坑，同时强调一些关键注意事项。

4.1 误区一：状态定义理解错误

最常见的误区是误解状态定义，比如将dp[i]定义为“第i间房屋被偷时的最高金额”，然后额外定义一个数组表示“第i间房屋不被偷时的最高金额”。这种定义方式虽然也能得到正确结果，但会增加代码的复杂度，而且容易混淆状态转移逻辑。

错误示例（状态定义冗余）：

def rob(nums): if not nums: return 0 n = len(nums) # dp_steal[i]：第i间房屋被偷时的最高金额 # dp_not_steal[i]：第i间房屋不被偷时的最高金额 dp_steal = [0] * n dp_not_steal = [0] * n dp_steal[0] = nums[0] dp_not_steal[0] = 0 for i in range(1, n): dp_steal[i] = dp_not_steal[i-1] + nums[i] dp_not_steal[i] = max(dp_steal[i-1], dp_not_steal[i-1]) return max(dp_steal[-1], dp_not_steal[-1])

这种代码虽然正确，但空间复杂度是O(n)，而且状态定义冗余。实际上，我们不需要单独记录“第i间房屋是否被偷”，因为dp[i] = max(dp[i-1], dp[i-2]+nums[i])已经隐含了这两种情况：dp[i-1]对应“不偷第i间”，dp[i-2]+nums[i]对应“偷第i间”。

解决方法：牢记标准状态定义——dp[i]表示“前i+1间房屋的最高金额”，专注于“最优子结构”，不需要关心具体哪间房屋被偷，这样能简化代码逻辑，也便于后续优化空间复杂度。