這篇文章將帶你一步步理解並解決 LeetCode 213: House Robber II 問題。這題是 LeetCode 198: House Robber 的變體，不過有一個額外的限制條件：房屋呈現環形排列，這就意味著第一間房子和最後一間房子相連。

題目：

你是一個職業小偷，打算搶劫一排房屋。每間房屋裡藏有一定數量的現金，你的目標是不要觸動警報系統，並搶劫最多的現金。

規則是：

• 兩間相鄰的房屋不能同時搶劫（避免觸動警報）。
• 房屋是圍成一個環形，也就是說，第一間房子與最後一間房子相連。

你需要計算你能搶劫的最大金額。

解題思路

因為房屋是環狀排列，所以如果搶劫了第一間房子，那麼最後一間房子就不能被搶劫。

由於環形排列，我們可以將問題拆解為兩個線性問題：

1. 不考慮第一間房子，搶劫第 2 到第 n 間房子。
2. 不考慮最後一間房子，搶劫第 1 到第 n-1 間房子。

最後取這兩個情況中能夠搶劫的最大金額即可。

這是因為在這兩種情況中，要麼搶第一間，不搶最後一間，要麼搶最後一間，不搶第一間。這樣的拆分方式，巧妙地將環形問題轉化成了兩個單一的線性問題。

直接把 198: House Robber 這題的作法拿來修改。

實作：

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);

        vector<int> nums1;
        nums1.assign(nums.begin(), nums.end()-1);
        vector<int> dp1(nums1.size());
        dp1[0] = nums1[0];
        dp1[1] = max(nums1[0], nums1[1]);
        for (int i = 2; i < nums1.size(); i++) {
            dp1[i] = max(dp1[i-1], dp1[i-2] + nums1[i]);
        }

        vector<int> nums2;
        nums2.assign(nums.begin()+1, nums.end());
        vector<int> dp2(nums2.size());
        dp2[0] = nums2[0];
        dp2[1] = max(nums2[0], nums2[1]);
        for (int i = 2; i < nums2.size(); i++) {
            dp2[i] = max(dp2[i-1], dp2[i-2] + nums2[i]);
        }

        return max(dp1[nums1.size()-1], dp2[nums2.size()-1]);
    }
};

優化一下，節省不必要的 nums 複製開銷，以及共同邏輯函式化，

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);

        int range1 = robRange(nums, 0, nums.size()-1);
        int range2 = robRange(nums, 1, nums.size());

        return max(range1, range2);
    }
private:
    int robRange(vector<int>& nums, int start, int end) {
        int n = end - start;
        vector<int> dp(n);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start+1]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-1], dp[i-2] + nums[start+i]);
        }
        return dp[n-1];
    }
};

時間複雜度：O(n)
空間複雜度：O(n)

將 dp 陣列也省下來，

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);

        int range1 = robRange(nums, 0, nums.size()-1);
        int range2 = robRange(nums, 1, nums.size());

        return max(range1, range2);
    }
private:
    int robRange(vector<int>& nums, int start, int end) {
        int n = end - start;
        int prev2 = nums[start]; // dp[i-2]
        int prev1 = max(nums[start], nums[start+1]); // dp[i-1]
        for (int i = 2; i < n; i++) {
            int curr = max(prev1, prev2 + nums[start+i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
};

時間複雜度：O(n)
空間複雜度：O(1)

參考：
#213. House Robber II