題目描述

同 3146：沿街房屋偷竊最大金額，相鄰不可同時偷。

一維 DP 狀態定義

maxV[i] 表示前 i 間房屋（0-based 到 i-1）的最大收益。轉移：

maxV[i] = max(maxV[i-2] + nums[i-1], maxV[i-1])

• 偷第 i-1 間：maxV[i-2] + nums[i-1]
• 不偷第 i-1 間：maxV[i-1]

初始：maxV[0]=0, maxV[1]=nums[0]。答案 maxV[n]。

關鍵證明：為何不需考慮 maxV[i-1] 不含 nums[i-2] 的情況？

若 maxV[i-1] 不含 nums[i-2]，則 maxV[i-1] = maxV[i-2]。此時 maxV[i-2] + nums[i-1] ≥ maxV[i-1]（因 nums[i-1] ≥ 0），偷當前房屋更優。故公式涵蓋所有情況。

代碼實現

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

空間優化

只需兩個變量 prev2, prev1 滾動更新，O(1) 空間。

與 3146 兩狀態法對比

本質等價，一維 DP 更簡練，二狀態法語義更清晰。