題目描述：來自LeetCode
思路：這道題和01背包很像，這件房屋偷不偷跟前一間房屋是否偷了有關，比如說這是第i間房屋，如果第i-1間房屋偷了，那第i間房屋就不能再偷，那最大值就跟前i-1間房屋的金額最大值有關，如果第i-1間房屋沒偷，那第i間房屋就可能要偷，且最大值跟前i-2間房屋有關，每一天偷與不偷，都跟前面的最大值有關，故可寫出狀態轉移方程dp[i]=max(dp[i-1],dp[i-2]+nums[2])，特殊的，當只有一間房屋，則一定偷，且最大值為dp[0]=nums[0],當只有兩件房屋，那一定是偷一間，且偷最大的那間，dp[1]=max(dp[0],dp[1])
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;//沒有房屋可偷
int n=nums.size();
if(n==1) return nums[0];//只有一間
vector<int> dp=vector<int>(n,0);
dp[0]=nums[0];
dp[1]=max(nums[0],nums[1]);
for(int i=2;i<nums.size();i++){
dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[n-1];
}優化，空間復雜度O(N)到O(1)
我們從狀態轉移方程可以發現，第i間房屋偷不偷只與第i-1天和第i-2天有關，因此，我們可以用滾動陣列，只記錄第i-1和第i-2天的最大值即可
int rob(vector<int>& nums) {
int beforeyesterday,yesterday;//前天i-2,昨天i-1
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
beforeyesterday=nums[0];
yesterday=max(nums[0],nums[1]);
for(int i=2;i<nums.size();i++){
int tmp=yesterday;
yesterday=max(beforeyesterday+nums[i],yesterday);
beforeyesterday=tmp;
}
return yesterday;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348652.html
標籤：其他