2023.8.20
本题是 打家劫舍 的进阶版,房屋之间形成一个环了,也就是第一个房屋和最后一个房屋不能一起偷了。那么能偷的情况分为下列三种:
- 不考虑偷首房间。
- 不考虑偷尾房间。
- 不考虑偷首尾房间。
第三种情况包含于第一和第二种情况了,所以分别为第一种和第二种情况设两个dp数组,再用昨天 打家劫舍 的思路做就行。 下面上代码:
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];
}
};
附上打的草稿以供参考:
文章来源:https://www.toymoban.com/news/detail-662873.html
文章来源地址https://www.toymoban.com/news/detail-662873.html
到了这里,关于leetcode 213. 打家劫舍 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!