目錄

• • 1、題目
  • 2、求解思路
  • 3、代碼

1、題目

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

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

2、求解思路

1、確定總目標：從0~nums.size()-1個房子中能偷到的最大金額
2、確定子問題：從 0~k 個房子中能偷到的最大金額,k=nums.size()-1就是原問題。（原問題要能由子問題表示。）
3、分析狀態方程：一個子問題的解要能通過其他子問題的解求出。
對于每個房屋，我們有兩種選擇：偷或者不偷；
如果選擇偷第i個房屋，那么第i-1個房屋肯定不能偷，問題轉化為前i-2個房屋中最大價值，最后再加上第i個房屋的價值，構成第前i個房屋中最大價值。
如果選擇不偷第i個房屋，那么第i-1個房屋肯定能偷，問題轉化為前i-1個房屋中最大價值，構成第前i個房屋中最大價值。
所以狀態方程確定：

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

4、邊界條件：
當只有一個房屋時，一定偷這個房屋。
當只有兩個房屋時，選擇偷兩個中價值較大的房屋。
5、空間優化
對于小偷問題，我們發現，最后一步計算 dp[i]的時候，實際上只用到了dp[i-1] 和 dp[i-2] 的結果。
那么，我們可以只用兩個變量保存兩個子問題的結果，就可以依次計算出所有的子問題。

int ScrollingArray[2]=0;
//循環開始時，ScrollingArray[1]表示 dp[i-1]，ScrollingArray[0]表示 dp[i-2]
for(int i=2;i<size;i++) 
{//dp[i] = max{ dp[i-1], dp[i-2] + nums[i] }int temp = max(ScrollingArray[1],ScrollingArray[0]+nums[i]);//dp[i-2] = dp[i-1];ScrollingArray[0]=ScrollingArray[1];//dp[i-1]=dp[i]ScrollingArray[1] = temp;
}

3、代碼

1、沒有滾動數組優化：

class Solution {
public:int rob(vector<int>& nums) {int size = nums.size();if(size==0) return 0;else if(size == 1) return nums[0];else if(size == 2) return max(nums[1],nums[0]);vector<int >dp(size,0);dp[0]=nums[0];dp[1]=max(nums[1],nums[0]);//對于每一個房間，有不偷和偷兩種結果，我們取價值最大的。for(int i=2;i<size;i++) dp[i]=max(dp[i-1],dp[i-2]+nums[i]);return dp[size-1];}
};

2、加了滾動數組優化;

class Solution {
public:int rob(vector<int>& nums) {int size = nums.size();if(size==0) return 0;else if(size == 1) return nums[0];else if(size == 2) return max(nums[1],nums[0]);int ScrollingArray[2]={0};ScrollingArray[0]=nums[0];ScrollingArray[1]=max(nums[1],nums[0]);//循環開始時，ScrollingArray[1]表示 dp[i-1]，ScrollingArray[0]表示 dp[i-2]for(int i=2;i<size;i++) {//dp[i] = max{ dp[i-1], dp[i-2] + nums[i] }int temp = max(ScrollingArray[1],ScrollingArray[0]+nums[i]);//dp[i-2] = dp[i-1];ScrollingArray[0]=ScrollingArray[1];//dp[i-1]=dp[i]ScrollingArray[1] = temp;}return ScrollingArray[1];}
};