題目描述

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。

示例 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 。

遞歸求解

思路：將問題進行分解成兩種情況，當前房屋搶或者不搶，如果搶了當前房屋，則下一個房屋不能搶。如果當前房屋不搶，則下一個房屋可以搶。

class Solution {
public:int rob(vector<int>& nums) {return rob_recusion(nums,nums.size()-1);}
private:int rob_recusion(vector<int>& nums, int index){//遞歸求解if(index < 0)return 0;//分解成兩個子問題//當前搶了下一家不能搶//當前沒有搶下一家可以搶int maxres = max(nums[index] + rob_recusion(nums, index-2),rob_recusion(nums, index-1));return maxres;}
};

把這個答案提交后，發現超出了時間限制，顯然是遞歸的次數太多導致的。繼續用記憶路徑的方法進行優化。

class Solution 
{
public:int rob(vector<int>& nums) {m_mem = vector<int>(nums.size()+1, -1);return rob_recusion(nums,nums.size()-1);}
private:int rob_recusion(vector<int>& nums, int index){//遞歸求解if(index < 0)return 0;//分解成兩個子問題//當前搶了下一家不能搶//當前沒有搶下一家可以搶if(m_mem[index] != -1)return m_mem[index];int maxres = max(nums[index] + rob_recusion(nums, index-2),rob_recusion(nums, index-1));m_mem[index] = maxres;return maxres;}vector<int> m_mem;
};

利用路徑記憶的方法進行優化后，再次提交之后就可以正常通過。

動態規劃

下面利用動態規劃進行進一步的優化。
根據上面路徑記憶的遞歸算法，可以得到動態規劃的迭代公式。
resmax[i] = max(nums[i] + resmax[i-2], resmax[i-1])加上對基準情況添加額外的判斷，可以得到如下的算法。

class Solution 
{
public:int rob(vector<int>& nums) {if(nums.size() == 0)return 0;if(nums.size() == 1)return nums[0];if(nums.size() == 2)return max(nums[0], nums[1]);vector<int> resmax(nums.size()+1, 0);//基準情況resmax[0] = nums[0];resmax[1] = max(nums[0], nums[1]);for(int index=2;index < nums.size();++index){resmax[index] =  max(nums[index] + resmax[index-2], resmax[index-1]);}return resmax[nums.size()-1];}
};

動態規劃解題步驟

動態規劃解題的關鍵是要能夠找到對應的子問題，將原問題進行分解，然后利用遞歸的方式實現，然后再將遞歸的解改寫成動態規劃。

1. 實現遞歸解
2. 實現帶路徑記憶的遞歸解（一般情況下已經可以滿足要求）
3. 改寫成動態規劃算法

轉載于:https://www.cnblogs.com/BlueskyRedsea/p/9251860.html

總結

以上是生活随笔為你收集整理的LeetCode-198. 打家劫舍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。