題目描述

沿街房屋各存金額 nums[i]，相鄰房屋有防盜系統連動，不能連續偷竊。求最大可偷金額。

動態規劃狀態定義

到第 i 間房屋，兩種狀態：

• selected[i]：偷第 i 間 → 必不偷 i-1，selected[i] = unselected[i-1] + nums[i]
• unselected[i]：不偷第 i 間 → 可偷可不偷 i-1，取最大：unselected[i] = max(selected[i-1], unselected[i-1])

初始：selected[0] = nums[0], unselected[0] = 0。答案 max(selected[n-1], unselected[n-1])。

代碼實現

class Solution {
public:
    int rob(vector& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        vector selected(n), unselected(n);
        selected[0] = nums[0];
        unselected[0] = 0;
        for (int i = 1; i < n; i++) {
            selected[i] = unselected[i-1] + nums[i];
            unselected[i] = max(selected[i-1], unselected[i-1]);
        }
        return max(selected[n-1], unselected[n-1]);
    }
};

空間優化 O(1)

只需保留前一狀態：

int rob(vector& nums) {
    int prev_yes = 0, prev_no = 0;
    for (int n : nums) {
        int cur_yes = prev_no + n;
        int cur_no = max(prev_yes, prev_no);
        prev_yes = cur_yes;
        prev_no = cur_no;
    }
    return max(prev_yes, prev_no);
}

另一視角：一維 DP

dp[i] = 前 i 間房屋最大金額。轉移：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])（dp[0]=0, dp[1]=nums[0]）。本質相同。

複雜度

• 時間：O(n)
• 空間：O(n) 數組版 / O(1) 優化版

擴展：House Robber II (環形街道)

首尾相連，分兩種情況：偷第一間（則不偷最後）、不偷第一間（可偷最後），取最大。見後續題目。