LeetCode 198：House Robber（打家劫舍）

一、題目描述

你是專業小偷，計劃搶劫一條街上的房屋。每間房有現金 nums[i]。相鄰房屋有防盜系統相連，不能同時搶劫相鄰兩間。求最大搶劫金額。

二、解題思路：動態規劃

狀態定義：dp[i] 表示搶劫前 i 間房的最大金額。
轉移：對於第 i 間房（0-indexed），兩種選擇：
- 不搶：dp[i] = dp[i-1]
- 搶：dp[i] = dp[i-2] + nums[i]
取最大值：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
初始：dp[0]=nums[0], dp[1]=max(nums[0],nums[1])。
可優化為兩個變量滾動數組，空間 O(1)。

三、代碼實現（C++）

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

四、複雜度分析

• 時間：O(N)
• 空間：O(1)

經典 DP 入門題，狀態轉移直觀，滾動數組優化空間。