LeetCode House Robber II：環狀房屋動態規劃

題目大意

房屋圍成一圈，首尾相鄰。每間房有非負金額，偷相鄰房會觸發警報。求最大可偷金額。

核心思路：拆環為鏈

首尾不能同時偷，分兩種情況取最大：

1. **不偷第一間**：問題退化為線性 House Robber I，範圍 [1, n-1]
2. **不偷最後一間**：範圍 [0, n-2]

答案 = max(rob_linear(1,n-1), rob_linear(0,n-2))

線性 House Robber 子問題

int rob_range(vector& nums, int l, int r) { // 閉區間 [l, r]
    int prev = 0, curr = 0;
    for (int i = l; i <= r; ++i) {
        int next = max(curr, prev + nums[i]);
        prev = curr;
        curr = next;
    }
    return curr;
}

int rob(vector& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    if (n == 2) return max(nums[0], nums[1]);
    return max(rob_range(nums, 0, n-2), rob_range(nums, 1, n-1));
}

原文雙向掃描法分析

原文提出從左向右、從右向左兩次 DP，比較 `d[n-1]` vs `d[n-2]` 和 `dr[1]`，邏輯等價但較繁瑣。拆環法更直觀。

複雜度

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

狀態轉移解析

`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`：
- 不偷第 i 間：沿用 `dp[i-1]`
- 偷第 i 間：必須不偷 i-1，加上 `dp[i-2] + nums[i]`

邊界情況處理