好像，自己讀的書確實有點少了。

——2024年7月2日

---

198. 打家劫舍 - 力扣（LeetCode）

題目描述

????????你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你?不觸動警報裝置的情況下?，一夜之內能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4。

示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12。

題解思路

? ? ? ? 動態規劃

????????利用動態規劃解題的時候，dp數組的含義都是自己定的，定好之后就需要思考自己如何實現，列出狀態轉移方程，題目就迎刃而解了。

?解法一

1. 定義dp數組含義；

? ? ? ? dp[i]表示偷取以 i 結尾的房間能夠獲取的最大價值。

2. 根據dp含義列出狀態轉移方程；

? ? ? ? 因為小偷不能偷取連續的兩個房間，那么如果偷取了第 i 個房間，第 i-1 間房間就不能偷取了，否則會觸發警報，但是 i-2 以前的所有房間都是可以偷取的，所以列出狀態轉移方程如下：
????????dp[i] = max( dp[0], dp[1], ..., dp[i - 2] ) + nums[i]；

3. 確定邊界條件；

? ? ? ??①如果只有一個房間，那么dp[0] = nums[0]；
????????②如果只有兩個房間，那么dp[1] = max(nums[0], nums[1])；

4.思考實現方式；

? ? ? ? 對于dp[i] = max( dp[0], dp[1], ..., dp[i - 2] ) + nums[i]如何實現呢？

????????思考這段方程的含義：這段方程是實現每次偷取第 i 個房間的時候選取前 i-2 個房間中能夠獲取的最大價值，考慮利用大根堆的優先隊列實現。

? ? ? ? 因為每次都要選取前 i - 2 個中的最大值，而大根堆的堆頂元素又是整個堆的最大值，可以考慮在 i = 2時開始向優先隊列中插入元素，這樣就能保證每次取出堆頂元素就是前 i - 2 個值中的最大值。

代碼實現

class Solution {
public:int rob(vector<int>& nums) {// 利用優先隊列和動態規劃完成 dp[i] = max(dp[0]...dp[i-2]) + nums[i]// dp[i]表示偷取以i結尾的房間的最大價值和int len = nums.size();priority_queue<int> pq;vector<int> dp(len, 0);dp[0] = nums[0];int maxValue = nums[0];for(int i = 1; i < len; i++){if(i >= 2){pq.push(dp[i-2]);}if(i == 1){dp[i] = max(nums[i-1], nums[i]);}else{dp[i] = pq.top() + nums[i];}maxValue = max(maxValue, dp[i]);}return maxValue;}
};

解法二

1. 定義dp數組含義；

????????dp[i]表示偷取前 i 個房間能夠獲得的最大價值；

2. 根據dp含義列出狀態轉移方程；

? ? ? ??每個房間都有偷與不偷兩種可能，那么在計算dp[i]的時候就會出現兩種情況；
????????①偷：dp[i] = dp[i-2] + nums[i]；//不能偷連續的兩個房間
? ? ? ? ②不偷：dp[i] = dp[i-1]；//如果不偷那么當前的最大價值就是dp[i-1]的最大價值。

3. 確定邊界條件；

? ? ? ??①如果只有一個房間，那么dp[0] = nums[0]；
????????②如果只有兩個房間，那么dp[1] = max(nums[0], nums[1])；

4.思考實現方式；

? ? ? ??這個相對于解法一就很好實現了，利用vector容器即可。

代碼實現

class Solution {
public:int rob(vector<int>& nums) {// dp[i]表示偷取前i的房間的最大價值和int len = nums.size();vector<int> dp(len, 0);dp[0] = nums[0];for(int i = 1; i < len; i++){if(i == 1){dp[i] = max(nums[0], nums[1]);}else{dp[i] = max(dp[i-1], dp[i-2] + nums[i]);}}return dp[len-1];}
};

結果展示

解法一	解法二