初始理解問題

首先，我們需要明確題目在問什么。題目“House Robber”描述的是一個強盜在一排房屋前，每個房屋都有一定數量的錢。強盜不能連續搶劫兩個相鄰的房屋，否則會觸發警報。目標是搶劫到最多的錢。

動態規劃的思路

這個問題可以使用動態規劃（Dynamic Programming, DP）來解決。動態規劃是一種分階段解決問題的方法，通常用于具有重疊子問題和最優子結構性質的問題。在這里，我們需要找到在不能連續搶劫兩個相鄰房屋的情況下，能夠獲得的最大金額。

DP數組的定義

在給定的代碼中，dp是一個數組，其中dp[i]表示到達第i個房屋時能夠搶劫到的最大金額。這里的“到達”并不意味著一定要搶劫第i個房屋，而是表示在前i個房屋中，按照規則能夠獲得的最大金額。

DP數組的初始化

1. 基本情況1：沒有房屋（nums.empty()）
   如果沒有房屋，那么能搶劫的最大金額自然是0。

   if (nums.empty()) {return 0;
   }
   

2. 基本情況2：只有一個房屋（size == 1）
   如果只有一個房屋，那么只能搶劫這個房屋，最大金額就是nums[0]。

   if (size == 1) {return nums[0];
   }
   

3. 基本情況3：兩個房屋
   如果有兩個房屋，強盜不能同時搶劫這兩個房屋，所以選擇金額較大的那個。

   dp[0] = nums[0];
   dp[1] = max(nums[0], nums[1]);
   

DP遞推關系

對于第i個房屋（i >= 2），有兩個選擇：

1. 搶劫第i個房屋：
   如果搶劫第i個房屋，那么不能搶劫第i-1個房屋。因此，最大金額為dp[i-2] + nums[i]（即前i-2個房屋的最大金額加上當前房屋的金額）。

2. 不搶劫第i個房屋：
   如果不搶劫第i個房屋，那么最大金額與前i-1個房屋的最大金額相同，即dp[i-1]。

為了最大化總金額，我們選擇這兩種情況中的較大值：

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

示例解析

假設nums = [2, 7, 9, 3, 1]：

1. 初始化：

   • dp[0] = 2（只有第一個房屋）
   • dp[1] = max(2, 7) = 7（第一或第二個房屋，選較大的）

2. 計算dp[2]：

   • 搶劫第三個房屋：dp[0] + nums[2] = 2 + 9 = 11
   • 不搶劫第三個房屋：dp[1] = 7
   • dp[2] = max(11, 7) = 11

3. 計算dp[3]：

   • 搶劫第四個房屋：dp[1] + nums[3] = 7 + 3 = 10
   • 不搶劫第四個房屋：dp[2] = 11
   • dp[3] = max(10, 11) = 11

4. 計算dp[4]：

   • 搶劫第五個房屋：dp[2] + nums[4] = 11 + 1 = 12
   • 不搶劫第五個房屋：dp[3] = 11
   • dp[4] = max(12, 11) = 12

最終，dp = [2, 7, 11, 11, 12]，返回dp[4] = 12。

為什么這樣定義dp[i]

dp[i]表示“考慮前i+1個房屋（因為索引從0開始）時能夠獲得的最大金額”。這個定義允許我們通過子問題的解來構建更大問題的解，這是動態規劃的核心思想。具體來說：

• dp[i]依賴于dp[i-1]和dp[i-2]，這表示當前的最大金額取決于前一個房屋和前兩個房屋的最大金額。
• 通過這種方式，我們可以確保不連續搶劫兩個相鄰的房屋，因為如果搶劫了i，就會跳過i-1，使用dp[i-2]。

時間復雜度和空間復雜度

• 時間復雜度：O(n)，因為我們只需要遍歷一次nums數組。
• 空間復雜度：O(n)，因為我們使用了一個大小為n的dp數組。實際上，可以優化到O(1)空間，因為dp[i]只依賴于dp[i-1]和dp[i-2]，可以用兩個變量代替整個數組。

可能的優化

可以優化空間復雜度，只保留前兩個狀態：

int rob(vector<int>& nums) {int prev = 0, curr = 0;for (int num : nums) {int temp = curr;curr = max(prev + num, curr);prev = temp;}return curr;
}

這樣，空間復雜度降為O(1)。

總結

• dp[i]表示“在前i+1個房屋中，按照規則能夠搶劫到的最大金額”。
• 通過比較“搶劫當前房屋”和“不搶劫當前房屋”兩種情況的最大值來更新dp[i]。
• 初始化dp[0]和dp[1]作為基礎情況。
• 最終結果是dp[n-1]，其中n是房屋的數量。

這種方法確保了我們在每一步都做出最優的選擇，從而在全局上得到最大的搶劫金額。