213. 打家劫舍 II

发表于 分类于 阅读次数： Waline： 本文字数： 850 阅读时长 ≈ 3 分钟

考点

  • 线性DP
  • 环形DP

思路

一、问题回顾

给定一个数组 nums，其中 nums[i] 表示第 i 个房屋中的金额。 小偷不能在同一晚偷取相邻的房屋。

与线性版本不同的是，本题中的房屋 首尾相连，即：

  • 第 0 个房屋与第 n-1 个房屋是相邻的

目标是：在不触发警报的前提下，偷取最大金额。

二、为什么不能直接在“环”上做 DP？

在线性版本中，状态定义通常为： \[ dp[i] = \max(dp[i-1], dp[i-2] + nums[i]) \] 其正确性依赖于一个前提：

是否选择第 \(i\) 个房屋，只与前两个位置有关。

但在环形结构中，第 0 个房屋是否被选择，会影响到第 \(n-1\) 个房屋是否合法。 这是一个全局约束，而不是局部状态能自然表达的约束。

如果强行在环上定义 DP：

  • 状态中必须额外记录「第 0 个房屋是否被选」
  • 会导致状态膨胀、转移复杂、实现困难

因此，本题的关键并不在于“如何在环上 DP”，而在于：

如何在建模阶段消除“环”的约束

三、最优解的四种情况分析

从是否选择首尾两个房屋的角度，所有可能的最优解可以分为四类：

  1. 有 0 且有 \(n-1\)
  2. 有 0 且无 \(n-1\)
  3. 无 0 且有 \(n-1\)
  4. 无 0 且无 \(n-1\)

其中：

  • 情况 1 非法（0 与 \(n-1\) 相邻）
  • 情况 2、3、4 合法

接下来观察如何覆盖这些合法情况。

四、化环为链：两次线性 DP 覆盖所有合法解

情况一：不选 \(n-1\)

在区间： \[ [0, n-2] \] 上做一次标准的线性「打家劫舍 I」DP。

该区间的最优解覆盖：

  • 有 0 且无 \(n-1\)
  • 无 0 且无 \(n-1\)

情况二：不选 0

在区间： \[ [1, n-1] \] 上再做一次线性 DP。

该区间的最优解覆盖：

  • 无 0 且有 \(n-1\)
  • 无 0 且无 \(n-1\)

结论

所有合法情况（2、3、4）都被覆盖，因此最终答案为： \[ \max\big(\text{rob}(0 \sim n-2),\ \text{rob}(1 \sim n-1)\big) \] 这并不是重复计算，而是对互斥端点的枚举。

五、线性 DP 的状态设计（区间长度 DP）

对于任意一个线性区间，其本质仍是经典问题： \[ f[i] = \max(f[i-1],\ f[i-2] + 当前房屋金额) \] 在实现中，可以将 f[i] 设计为：

  • 前 i 个房屋（按区间顺序）所能获得的最大收益

这样可以避免直接使用原数组下标，减少越界和 off-by-one 错误。

六、AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    static const int maxn = 1e2 + 5;

    int rob(vector<int>& nums) {
        int n = nums.size();
        int f[maxn];

        // ---------- 情况一：不选 n-1，区间 [0, n-2] ----------
        // f[i] 表示前 i 个房屋（对应 nums[0..i-1]）的最大收益
        f[0] = 0;
        f[1] = nums[0];

        int res = nums[0];
        for (int i = 2; i <= n - 1; ++i) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]);
            res = max(res, f[i]);
        }

        // 特判：只有一个房屋
        if (n == 1)
            return res;

        // ---------- 情况二：不选 0，区间 [1, n-1] ----------
        // 此时 f[i] 表示前 i-1 个房屋（对应 nums[1..i-1]）的最大收益
        f[1] = 0;
        f[2] = nums[1];
        res = max(res, nums[1]);

        for (int i = 3; i <= n; ++i) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]);
            res = max(res, f[i]);
        }

        return res;
    }
};