LeetCode 198 打家劫舍：動態規劃求最大收益

---

題目描述

你是一名專業小偷，計劃沿街搶劫房屋。每間房屋存放一定現金，相鄰房屋裝有防盜系統，若連續搶劫兩間相鄰房屋會觸發報警。給定非負整數數組表示每間房屋金額，求不觸發報警前提下的最大搶劫金額。

範例：

輸入: [1,2,3,1]
輸出: 4 (搶劫第 0 和第 2 間房屋)

輸入: [2,7,9,3,1]
輸出: 12 (搶劫第 0、2、4 間)

解題思路：動態規劃 - 狀態壓縮

對於第 i 間房屋，只有兩種選擇：搶或不搶。

• 搶第 i 間：則第 i-1 間不能搶，收益 = dp[i-2] + nums[i]
• 不搶第 i 間：收益 = dp[i-1]

狀態轉移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

只需保留前兩個狀態，空間優化至 O(1)。

C++ 參考實現（遞歸 + 迭代雙版本）

class Solution {
public:
    // 迭代版：空間 O(1)
    int rob(vector& nums) {
        int prev2 = 0, prev1 = 0; // dp[i-2], dp[i-1]
        for (int num : nums) {
            int curr = max(prev1, prev2 + num);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
    
    // 遞歸版：尾遞歸優化
    int robRecursive(vector& nums) {
        return robHelper(nums, 0, 0, 0);
    }
    
    int robHelper(vector& nums, int i, int dp1, int dp2) {
        if (i >= nums.size()) return dp2;
        return robHelper(nums, i + 1, dp2, max(dp1 + nums[i], dp2));
    }
};

Python 參考實現

class Solution:
    def rob(self, nums):
        prev2 = prev1 = 0
        for num in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + num)
        return prev1
    
    # 一行式（利用 reduce）
    from functools import reduce
    def rob_one_line(self, nums):
        return reduce(lambda p, n: (p[1], max(p[1], p[0] + n)), nums, (0, 0))[1]

核心要點總結

• 狀態定義：dp[i] 表示前 i 間房屋的最大收益
• 選擇邏輯：搶當前 vs 不搶當前，取最大值
• 空間優化：滾動數組/兩變量滾動，O(1) 空間
• 變體延伸：LeetCode 213 (環形)、337 (二叉樹)、房屋染色等均為此模式變體

打家劫舍是動態規劃入門的經典題目，掌握「狀態轉移 + 空間壓縮」套路，舉一反三解決同類最優子結構問題。