題目
#

leetcode 213 - House Robber II (題目說明請點連結)

題目簡述
#

給一個整數陣列 nums，代表每間房屋中存放的金錢數量。你是一個專業的搶劫犯，計劃搶劫沿街的房屋。
每間房屋都裝有相互連接的防盜系統，如果兩間相鄰的房屋在同一晚上被搶劫，防盜系統就會觸發警報。
額外限制：所有房屋都圍成一個圓圈，這意味著第一間房屋和最後一間房屋是相鄰的。
給定代表每間房屋存放金額的非負整數陣列，計算你在不觸發警報的情況下，今晚能夠搶劫到的最大金額。

範例
#

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: 你不能搶劫第一間房屋（金額 = 2），然後搶劫第三間房屋（金額 = 2），因為它們是相鄰的。
你只能搶劫第二間房屋（金額 = 3）。

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: 搶劫第一間房屋（金額 = 1），然後搶劫第三間房屋（金額 = 3）。
總金額 = 1 + 3 = 4。

Example 3:

Input: nums = [1,2,3]
Output: 3
Explanation: 搶劫第二間房屋（金額 = 2），或者搶劫第一間和第三間房屋（金額 = 1 + 3 = 4），但第一間和第三間是相鄰的。

解題思路
#

這題是 leetcode 198 - House Robber 的進階版本，增加了房屋圍成圓圈的限制。由於第一間房屋和最後一間房屋是相鄰的，我們不能同時搶劫它們。因此，我們需要將問題分解為兩種情況：

不搶劫第一間房屋：搶劫範圍為 [1, n-1]
不搶劫最後一間房屋：搶劫範圍為 [0, n-2]

解法
#

將環形陣列問題分解為兩個線性陣列問題
分別計算兩種情況下的最大金額
返回兩種情況中的最大值
使用與 leetcode 198 相同的動態規劃方法

步驟
#

問題分解：
- 情況 1：不搶劫第一間房屋，搶劫範圍 [1, n-1]
- 情況 2：不搶劫最後一間房屋，搶劫範圍 [0, n-2]
動態規劃：
- 對於每種情況，使用與 leetcode 198 相同的演算法
- 對於每個位置 i，計算 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- 創建 dp 陣列，計算每個位置能夠搶劫到的最大金額
返回結果：
- 比較兩種情況的結果，返回最大值

例子說明
#

nums = [1,2,3,1]

情況	搶劫範圍	陣列	動態規劃過程	最大金額
情況 1	[1,3]	[2,3,1]	dp[0]=2, dp[1]=3, dp[2]=3	3
情況 2	[0,2]	[1,2,3]	dp[0]=1, dp[1]=2, dp[2]=4	4

最終結果： max(3, 4) = 4

搶劫策略說明：

情況 1：不搶劫第一間房屋，搶劫範圍 [2,3,1]
- 搶劫第二間房屋（金額 = 2）
- 搶劫第四間房屋（金額 = 1）
- 總金額 = 2 + 1 = 3
情況 2：不搶劫最後一間房屋，搶劫範圍 [1,2,3]
- 搶劫第一間房屋（金額 = 1）
- 搶劫第三間房屋（金額 = 3）
- 總金額 = 1 + 3 = 4

完整程式碼
#

java

class Solution {
    public int rob(int[] nums) {
        // 邊界條件：如果只有一間房屋，直接返回其金額
        if(nums.length == 1) {
            return nums[0];
        }
        
        // 邊界條件：如果有兩間房屋，返回金額較大的那一間
        if(nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }

        // 比較兩種情況：
        // 1. 不搶第一間 → [1..n-1]
        // 2. 不搶最後一間 → [0..n-2]
        return Math.max(robber(nums, 1, nums.length - 1), 
                       robber(nums, 0, nums.length - 2));
    }

    // 輔助方法：計算指定範圍內能夠搶劫到的最大金額
    public int robber(int[] nums, int start, int end){
        int len = end - start + 1;  // 計算範圍長度
        
        // 創建動態規劃陣列
        int[] dp = new int[len];
        
        // 設定基礎情況
        dp[0] = nums[start];                                    // 第一間房屋
        dp[1] = Math.max(nums[start], nums[start + 1]);         // 第二間房屋

        // 動態規劃，計算每個位置能夠搶劫到的最大金額
        for(int i = 2; i < len; i++){
            // 對於每個位置，選擇不搶劫當前房屋（dp[i-1]）
            // 或者搶劫當前房屋加上前兩間房屋的收益（dp[i-2] + nums[start+i]）
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[start + i]);
        }

        // 返回指定範圍內能夠搶劫到的最大金額
        return dp[len - 1];
    }
}

時間複雜度
#

時間複雜度：O(n)，其中 n 是陣列的長度
- 需要計算兩種情況，每種情況的時間複雜度為 O(n)
- 總時間複雜度仍為 O(n)
空間複雜度：O(n)，需要儲存動態規劃陣列
- 每種情況都需要創建一個長度為 n 的陣列
- 但由於兩種情況不會同時執行，實際空間複雜度仍為 O(n)