這個題主要解法和1是一樣的，都是動態規劃，建立一個2xn的二維陣列，一行表示偷，一行表示不偷，
遞推公式：
i號房子偷，那么i-1號房子必不能偷，i號房子不偷，則當前最大金額值為偷到i-1號房子時偷和不偷的最大值
當前房子選擇偷：dp[1][i] = dp[0][i-1]
當前房子不偷：dp[0][i] = max(dp[0][i-1],dp[1][i-1])
那么max(dp[0][n-1],dp[1][n-1])就是答案
此題與之不同的是，最后一個房子和第一個房子接上了，圍成了一圈，
分析：
圍成圈，并不影響到內部房子，僅僅影響了第一個房子和最后一個房子，
也就是說，第一個房子如果被偷了，那么最后一個房子就不能偷了，
乍一看，我們上面的式子，并沒有明確保留某一間房子偷還是沒偷的資訊，
但實際上，我們上面去得到偷取的最大金額，并不在乎某一個房子偷沒偷，僅僅在乎是在哪一個區間去偷，
這樣就很好辦了，直接搜兩次，一次范圍為[0, (n-1) -1],另一次范圍為[1,n-1]
class Solution {
int stolen(vector<int>& nums,int start,int end)
{
int n = nums.size();
vector<vector<int>> dp(2,vector<int>(n));
dp[0][start] = 0;
dp[1][start] = nums[start];
for(int i = start+1; i < end; ++i)
{
dp[0][i] = max(dp[1][i-1],dp[0][i-1]);
dp[1][i] = dp[0][i-1]+nums[i];
}
return max(dp[0][end-1],dp[1][end-1]);
}
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==0) return NULL;
if(n==1) return nums[0];
return max(stolen(nums,0,n-1),stolen(nums,1,n));
}
};
T.T,想不到，只能記住了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/276579.html
標籤：其他
上一篇：網站需要更換服務器應該怎么做？