題目
#

題目簡述
#

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

範例
#

Example 1:

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

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: 搶劫第 1 間房屋（金額 = 2），搶劫第 3 間房屋（金額 = 9），搶劫第 5 間房屋（金額 = 1）。
總金額 = 2 + 9 + 1 = 12。

Example 3:

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

解題思路
#

這題要求我們在不搶劫相鄰房屋的情況下，找到能夠搶劫到的最大金額。我們可以使用動態規劃（Dynamic Programming）來解決這個問題，通過建立一個陣列來記錄每個位置能夠搶劫到的最大金額。

解法
#

創建一個陣列 dp，其中 dp[i] 表示搶劫到第 i 間房屋時能夠獲得的最大金額
設定基礎情況：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])
對於每個位置 i，計算 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
返回 dp[nums.length-1]

步驟
#

初始化：
- 創建陣列 dp，長度為 nums.length
- 設定 dp[0] = nums[0]（第一間房屋）
- 設定 dp[1] = max(nums[0], nums[1])（第二間房屋）
動態規劃：
- 遍歷陣列，從索引 2 開始
- 對於每個位置 i，計算 dp[i] = max(dp[i-1], dp[i-2] + nums[i])
返回結果：
- 返回 dp[nums.length-1]

例子說明
#

nums = [1,2,3,1]

步驟	位置 i	nums[i]	dp[i-1]	dp[i-2] + nums[i]	dp[i]	說明
初始化	0	1	-	-	1	第一間房屋
初始化	1	2	1	2	2	第二間房屋，選擇最大值
第 1 步	2	3	2	1+3=4	4	選擇 dp[i-2] + nums[i]
第 2 步	3	1	4	2+1=3	4	選擇 dp[i-1]

最終結果： 4

搶劫策略說明：

位置 0：搶劫第一間房屋，獲得 1
位置 1：搶劫第二間房屋，獲得 2（比第一間多）
位置 2：搶劫第三間房屋，加上第一間房屋的收益，總共 1+3=4
位置 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]);
        }

        // 創建動態規劃陣列
        int[] dp = new int[nums.length];
        
        // 設定基礎情況
        dp[0] = nums[0];                                    // 第一間房屋
        dp[1] = Math.max(nums[0], nums[1]);                 // 第二間房屋

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

        // 返回最後一間房屋能夠搶劫到的最大金額
        return dp[nums.length-1];
    }
}