一文搞懂打家劫舍：状态设计与环形街道解法

问题背景：为什么打家劫舍是动态规划入门必刷题

LeetCode 的 House Robber（打家劫舍）系列表面上是在“偷房子”，本质考察的是不相邻元素最大和。给定一排房屋金额 nums，如果选择下标 i，就不能选择 i-1 和 i+1，目标是在约束下获得最大收益。

很多同学第一次做能写出递归，第二次又忘记状态转移；遇到环形街道、二叉树房屋、房屋有费用等变体时更容易混乱。真正需要掌握的不是某一道题的答案，而是以下三个动态规划核心问题：

1. 状态表示什么：dp[i] 是前 i 间房的最优解，还是第 i 间房“偷/不偷”的最优解？
2. 选择从哪里来：当前房屋偷与不偷，分别由哪些前置状态转移？
3. 约束如何影响答案：环形街道中首尾房屋相邻，普通线性 DP 的答案可能同时选中首尾，必须额外处理冲突。

本文先用标准线性问题建立状态模型，再推广到环形街道变体，最后给出可直接运行的 Python 代码和实战避坑清单。

方案对比：递归记忆化、一维 DP 与滚动数组

方法一：递归 + 记忆化搜索

定义 dfs(i) 表示考虑前 i 间房屋时能获得的最大金额。对于第 i 间房：

• 不偷：收益为 dfs(i-1)；
• 偷：第 i-1 间不能偷，收益为 dfs(i-2) + nums[i]。

因此有：

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

记忆化后时间复杂度为 O(n)，空间复杂度为递归栈加缓存的 O(n)。它适合帮助理解“选或不选”，但在面试中容易写出重复子问题未缓存、递归边界混乱等问题。

方法二：一维动态规划

设 dp[i] 表示前 i 间房屋能够偷到的最大金额。为了让下标和房屋编号对应，可以把 dp 长度设为 n + 1：

• dp[0] = 0：没有房屋时收益为 0；
• dp[1] = nums[0]：只有一间房时只能偷它；
• dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。

这种写法边界清晰，不需要在循环中频繁判断 i - 2 是否越界。

方法三：滚动数组优化空间

由于每次只依赖前两个状态，可以使用 prev2 和 prev1：

• prev2：再往前一间房的最优收益；
• prev1：上一间房为止的最优收益；
• cur = max(prev1, prev2 + num)。

滚动后空间复杂度降为 O(1)，也是工程和面试中最推荐的写法。

实操步骤：线性街道的标准动态规划写法

下面代码同时给出一维 DP 与滚动数组版本。二者状态含义完全一致，区别只在空间优化。

from typing import List


def rob_dp(nums: List[int]) -> int:
    """一维 DP：dp[i] 表示前 i 间房的最大收益。"""
    n = len(nums)
    if n == 0:
        return 0

    dp = [0] * (n + 1)
    dp[1] = nums[0]

    for i in range(2, n + 1):
        # 当前房屋金额是 nums[i - 1]
        rob_current = dp[i - 2] + nums[i - 1]
        skip_current = dp[i - 1]
        dp[i] = max(rob_current, skip_current)

    return dp[n]


def rob_rolling(nums: List[int]) -> int:
    """滚动数组：只保留前两个状态，空间复杂度 O(1)。"""
    prev2 = 0  # dp[i - 2]
    prev1 = 0  # dp[i - 1]

    for money in nums:
        current = max(prev1, prev2 + money)
        prev2, prev1 = prev1, current

    return prev1


if __name__ == "__main__":
    sample = [2, 7, 9, 3, 1]
    print(rob_dp(sample))       # 12
    print(rob_rolling(sample))  # 12

复杂度分析

• 时间复杂度：每间房屋只处理一次，因此为 O(n)。
• 空间复杂度：一维 DP 为 O(n)；滚动数组只使用两个变量，为 O(1)。
• 状态转移复杂度：每个状态只有“偷”和“不偷”两个来源，转移为 O(1)。

需要特别说明的是，prev2 和 prev1 初始都为 0，配合 Python 的并行赋值，可以自然处理空数组、单元素和双元素场景，不需要写很多分支。

环形街道变体：首尾不能同时选择怎么办

House Robber II 把房屋首尾相连，导致 nums[0] 和 nums[n-1] 也具有相邻关系。普通线性 DP 只会禁止物理下标相邻，即 0 与 1、1 与 2，却不会禁止 0 与 n-1。因此不能直接调用一次线性 DP。

关键处理方式是把环形约束拆成两个线性区间：

1. 不偷第一间房：考虑区间 nums[1:]，最后一间房可以自由选择；
2. 不偷最后一间房：考虑区间 nums[:-1]，第一间房可以自由选择。

最终答案为：

max(rob(nums[1:]), rob(nums[:-1]))

为什么这两种情况覆盖全部合法答案？因为任何合法方案都不可能同时偷首尾，那么它必然属于“不偷第一间”或“不偷最后一间”中的至少一种。两个区间取最大值不会漏掉最优解；同一个合法方案即使在两种情况中都可出现，也只是重复参与比较，不会造成错误。

环形问题代码如下：

from typing import List


def rob_linear(nums: List[int]) -> int:
    """线性街道：房屋不能相邻。"""
    prev2 = prev1 = 0
    for money in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + money)
    return prev1


def rob_circle(nums: List[int]) -> int:
    """环形街道：第一间和最后一间也相邻。"""
    if len(nums) == 1:
        return nums[0]

    # 拆掉第一间或最后一间，把环形约束降级为线性问题
    return max(
        rob_linear(nums[1:]),    # 不偷第一间
        rob_linear(nums[:-1])    # 不偷最后一间
    )


if __name__ == "__main__":
    print(rob_circle([2, 3, 2]))      # 3
    print(rob_circle([1, 2, 3, 1]))   # 4
    print(rob_circle([1, 2, 3]))      # 3

环形版本复杂度分析

• 时间复杂度：两个区间各扫描一次，总计仍是 O(n)。
• 空间复杂度：切片会产生 O(n) 额外空间；若追求严格 O(1)，可以给 rob_linear 增加左右边界参数，在原数组上扫描。
• 正确性核心：通过强制排除首房或尾房，消除首尾同时被选择的可能性。

状态设计进阶：什么时候需要二维状态

基础题中 dp[i] 直接表示前 i 间房的最大收益，已经足够。但如果题目增加“连续偷两次会报警”“偷某间房需要交手续费”“冷却一天”等条件，单一最优值可能无法记录当前房屋是否被选择。

这时更通用的状态设计是：

dp[i][0]：第 i 间房不偷时的最大收益
dp[i][1]：第 i 间房偷时的最大收益

转移关系为：

dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i]

在普通打家劫舍中，这两个状态可以合并成一个 dp[i]；但在限制更复杂时，二维状态能明确保留“上一步做了什么”。学习系列题时建议先用二维状态理解选择，再在约束简单时压缩成一维或滚动变量。

避坑总结：高频错误现象与修正方法

1. 初始化错位导致答案偏小或负索引

常见错误是直接写 dp[0] = nums[0]，循环又从 1 开始，并访问 dp[i - 2]。当 i = 1 时会访问 dp[-1]，在 Python 中虽然可能不报错，但会取到数组末尾元素，产生隐蔽错误。

修正方法有两种：

• 使用前 i 间房语义：dp 长度为 n + 1，单独设置 dp[1] = nums[0]；
• 或使用滚动数组，让 prev2 = prev1 = 0，从第一个金额开始遍历。

2. 环形题忘记处理只有一间房

对 nums = [5] 使用切片：

max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

两个空数组都会返回 0，最终错误地得到 0，而正确答案应为 5。原因是拆分区间时把唯一房屋同时从两种情况中排除了。

修正方法是在环形函数开头加入：

if len(nums) == 1:
    return nums[0]

3. 把“不能相邻”误写成贪心选择局部最大值

有同学看到金额为正，就尝试“遇到大的就偷”，例如 [2, 1, 1, 2]。贪心可能选择第一个 2 和第三个 1，得到 3；但选择第一个和第四个 2 可得 4。

局部最大不等于全局最优，因为当前选择会影响后续位置。修正方法是坚持动态规划转移：

max(不偷当前, 偷当前 + 跳过前一间的最优解)

4. 滚动数组更新顺序写反

错误写法：

prev2 = prev1
prev1 = max(prev1, prev2 + money)

第一行已经覆盖了旧的 prev2，第二行计算时使用的是新值，相当于允许连续偷相邻房屋。正确方式是使用并行赋值：

prev2, prev1 = prev1, max(prev1, prev2 + money)

等号右侧会先利用旧值完成计算，再统一更新，状态推进才正确。

5. 环形问题只拆一个区间

只计算 nums[1:] 会强制排除第一间房，如果最优方案恰好偷第一间、不偷最后一间，就会漏掉答案；只计算 nums[:-1] 同理。必须分别构造“不偷首房”和“不偷尾房”两种情况，再取最大值。

结语

打家劫舍系列的价值不在题目本身，而在于它提供了动态规划最经典的状态设计模板：先定义清楚状态，再枚举当前选择，最后处理初始化和特殊约束。线性版本可以压缩到两个变量，环形版本则通过区间拆分消除首尾冲突。掌握这套思路后，再遇到不相邻最大和、冷却期、费用选择等变体，就能从状态表示出发稳定推导，而不是死记转移方程。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。