2023.8.20
? ? ? ? ?本題是?打家劫舍?的進階版，房屋之間形成一個環(huán)了，也就是第一個房屋和最后一個房屋不能一起偷了。那么能偷的情況分為下列三種：
- 不考慮偷首房間。
- 不考慮偷尾房間。
- 不考慮偷首尾房間。
? ? ? ? 第三種情況包含于第一和第二種情況了，所以分別為第一種和第二種情況設(shè)兩個dp數(shù)組，再用昨天?打家劫舍?的思路做就行。 下面上代碼：
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
vector<int> dp1(nums.size());
vector<int> dp2(nums.size());
dp1[0] = dp2[0] = 0;
dp1[1] = nums[0];
dp2[1] = nums[1];
for(int i=2; i<=nums.size()-1; i++)
{
dp1[i] = max(dp1[i-1] , dp1[i-2]+nums[i-1]);
}
for(int i=2; i<=nums.size()-1; i++)
{
dp2[i] = max(dp2[i-1] , dp2[i-2]+nums[i]);
}
if(dp1[nums.size()-1] > dp2[nums.size()-1]) return dp1[nums.size()-1];
else return dp2[nums.size()-1];
}
};? ? ? ? 附上打的草稿以供參考：
文章來源：http://www.zghlxwxcb.cn/news/detail-662873.html
?文章來源地址http://www.zghlxwxcb.cn/news/detail-662873.html
到了這里，關(guān)于leetcode 213. 打家劫舍 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
