LeetCode 213：House Robber II（環形打家劫舍）

一、題目描述

房屋圍成一圈，首尾相鄰。其他同 House Robber。求最大搶劫金額。

二、解題思路：拆環為鏈

首尾不能同時搶。分兩種情況取最大：
1. 搶第 0 間，不搶第 n-1 間 → 範圍 [0, n-2]
2. 不搶第 0 間，可搶第 n-1 間 → 範圍 [1, n-1]
對兩個線性區間分別用 House Robber DP 求解，取較大值。
邊界：n=0→0, n=1→nums[0]。

三、代碼實現（C++）

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        return max(robRange(nums, 0, n-2), robRange(nums, 1, n-1));
    }
private:
    int robRange(vector& nums, int l, int r) {
        int prev2 = 0, prev1 = 0;
        for (int i = l; i <= r; ++i) {
            int cur = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
};

四、複雜度分析

• 時間：O(N)
• 空間：O(1)

將環形問題轉化為兩個線性子問題，復用線性 DP 邏輯。