LeetCode House Robber II：環形房屋動態規劃，拆環為鏈

問題描述

房屋圍成一圈（首尾相連），不能偷相鄰房屋。求最大盜竊金額。
House Robber I 是線性街道，本題是環形變體。

核心思想：拆環為鏈

環形約束：第 0 間和第 n-1 間不能同時偷。
分兩種互斥情況，取最大值：

1. 不偷第 0 間 → 考慮區間 [1, n-1]（線性）
2. 不偷第 n-1 間 → 考慮區間 [0, n-2]（線性）

兩種情況覆蓋所有合法方案，且互不重疊。答案 = max(rob_linear(0, n-2), rob_linear(1, n-1))。

線性區間 DP：O(1) 空間滾動數組

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 preNo = 0, preYes = 0; // 前一間：不偷/偷 的最大值
        for (int i = l; i <= r; ++i) {
            int curNo = max(preNo, preYes); // 當前不偷
            int curYes = preNo + nums[i];   // 當前偷
            preNo = curNo;
            preYes = curYes;
        }
        return max(preNo, preYes);
    }
};

狀態轉移圖解

第 i 間：
  不偷：max(前一間偷, 前一間不偷)
  偷：前一間必不偷 + nums[i]

複雜度

• 時間：O(n)，兩次線性掃描。
• 空間：O(1)，僅常數變量。

邊界情況處理

總結

House Robber II 的精髓在於將環形約束轉化為兩個線性子問題。這是處理環形 DP 的通用技巧：固定一個節點的狀態（選/不選），拆開環。同技巧適用於「環形房屋粉刷」、「環形最大子數組和」等問題。