198. House Robber

題目：
你是一個小偷，要偷一排房子，每間房子都有一些錢。
但不能偷相鄰的兩間房子（會觸發警報 ）
請問：最多可以偷多少錢？

範例：

• Example 1:
  Input: nums = [1,2,3,1]
  Output: 4
  Explanation: Rob house 1 (money = 1) and then rob
  house 3 (money = 3).
  Total amount you can rob = 1 + 3 = 4.

• Example 2:
  Input: nums = [2,7,9,3,1]
  Output: 12
  Explanation: Rob house 1 (money = 2), rob house 3
  (money = 9) and rob house 5 (money = 1).

想法：
只有一間房就偷他，如果兩間就偷錢比較多的那間

程式碼：

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;       // 沒房子
        if (n == 1) return nums[0]; // 只有一間

        int[] dp = new int[n];
        dp[0] = nums[0];                      // 只有第0間能偷的最大值
        dp[1] = Math.max(nums[0], nums[1]);   // 前兩間選較大值

        for (int i = 2; i < n; i++) {
            // 要麼不偷第 i 間（dp[i-1]），要麼偷第 i 間（dp[i-2] + nums[i]）
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];                   
    }
}

對於第 i 間房，有兩種選擇：

1. 不偷第 i 間 →
那最多金額就跟前一間一樣：dp[i - 1]
2. 偷第 i 間 →
就不能偷第 i-1 間，所以是：「第 i 間的錢 + dp[i - 2]」

公式：
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

實際操作：
初始：nums = [2,7,9,3,1]，n=5

Step1:
dp[0] = 2
dp[1] = max(2,7) = 7
i=2：dp[2] = max(7, 2+9) = 11 → 偷第2間
——＞dp = [2, 7, 11, ...]

Step2:
i=3：dp[3] = max(11, 7+3) = 11 → 不偷第3間
——＞dp 現在 [2,7,11,11,...]

Step3:
i=4：dp[4] = max(11, 11+1) = 12 → 偷第4間
——＞dp 最終 [2,7,11,11,12]

結果：dp[4] = 12
最佳策略舉例：偷第0、2、4 → 2+9+1 = 12