打家劫舍 II 图解题解

这道题到底在问什么

nums

[1, 2, 3, 1]

输出

4 （偷第 1、3 家 = 1 + 3）

先想最直接的笨办法

处理环形约束的常用招：枚举「断开点 / 哪个端点不选」，把环拆成几个线性问题分别解、再合并。环形子数组最大和也用这招。（动画第 16 步）

最优解：一步一步想明白

1. 3转折点：环的麻烦只在「首尾相邻」这一处。只要强行让首尾有一个不偷，环就断成了直线。于是分两种：① 偷范围 [0…n−2]（放弃最后一家）；② 偷范围 [1…n−1]（放弃第一家）。两种都用打家劫舍 I 的直线 DP，取较大者。直线 DP 的递推是 cur = max(prev1, prev2 + x)：要么不偷这家(沿用 prev1)，要么偷它(prev2 + 这家钱)。
2. 4对 [1,2,3] 跑直线DP情况①：把最后一家（下标 3）划掉（灰），只在前三家里偷。滚动变量 prev2=0、prev1=0。逐家推一遍。
3. 5cur = max(0, 0+1) = 1第 0 家：不偷=0，偷它=prev2+1=1。取大得 1。滚动更新 prev2=0、prev1=1。
4. 6cur = max(1, 0+2) = 2第 1 家：不偷=prev1=1，偷它=prev2+2=0+2=2（偷它就不能偷相邻的第 0 家）。取大得 2。更新 prev2=1、prev1=2。
5. 7cur = max(2, 1+3) = 4第 2 家：不偷=2，偷它=prev2+3=1+3=4。取大得 4——正是偷第 0、2 家（1+3）。情况① 答案 = 4。
6. 8对 [2,3,1] 跑直线DP情况②：换成把第一家（下标 0）划掉（灰），只在后三家里偷。滚动变量清零，重跑一遍。
7. 9cur = max(0, 0+2) = 2从第 1 家起：偷它=2 比不偷=0 好，得 2。更新 prev2=0、prev1=2。
8. 10cur = max(2, 0+3) = 3第 2 家：偷它=prev2+3=0+3=3，比留着第 1 家的 2 更划算。得 3。更新 prev2=2、prev1=3。
9. 11cur = max(3, 2+1) = 3第 3 家：偷它=prev2+1=2+1=3，和不偷的 3 打平——偷它并不更好。情况② 答案 = 3（就守住偷第 2 家的 3）。
10. 12max(4, 3) = 4两种情况取大：max(4, 3) = 4，对应偷第 0、2 家。这就是环形版的答案——拆环带来的额外代价，只是把直线 DP 跑了两遍。
11. 13直线版 rob：prev2、prev1 滚动，cur = max(prev1, prev2 + x)。环形版只是把它调用两次、传不同区间，再取最大。
12. 16处理环形约束的常用招：枚举「断开点 / 哪个端点不选」，把环拆成几个线性问题分别解、再合并。环形子数组最大和也用这招。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def rob(self, nums):
        if len(nums) == 1:              # 只有一家：两条线都会变空，单独处理
            return nums[0]
        def rob_line(arr):              # 直线版打家劫舍(LC198)
            prev, cur = 0, 0
            for x in arr:
                prev, cur = cur, max(cur, prev + x)   # 偷:prev+x / 不偷:cur
            return cur
        # 弃尾[0..n-2] 与 弃首[1..n-1] 两种，取较大
        return max(rob_line(nums[:-1]), rob_line(nums[1:]))

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];          // 只有一家，单独处理
        return max(robLine(nums, 0, n - 2),  // 弃尾
                   robLine(nums, 1, n - 1)); // 弃首
    }
    int robLine(vector<int>& nums, int l, int r) {
        int prev = 0, cur = 0;
        for (int i = l; i <= r; i++) {
            int t = max(cur, prev + nums[i]);
            prev = cur; cur = t;
        }
        return cur;
    }
};

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];          // 只有一家，单独处理
        return Math.max(robLine(nums, 0, n - 2),  // 弃尾
                        robLine(nums, 1, n - 1)); // 弃首
    }
    int robLine(int[] nums, int l, int r) {
        int prev = 0, cur = 0;
        for (int i = l; i <= r; i++) {
            int t = Math.max(cur, prev + nums[i]);
            prev = cur; cur = t;
        }
        return cur;
    }
}

# 环形 = 固定某端点的取舍，拆成线性各算一次
def solve_line(arr): ...      # 先写好线性版
ans = max(solve_line(去掉首),  # 情况A
          solve_line(去掉尾))  # 情况B

复杂度

面试官可能追问