题目:
文章来源地址https://www.toymoban.com/news/detail-605300.html
思路:
在版本一中增加了一个条件 那就是首尾相关联。那么只需要进行两次循环即可。
第一次是循环是偷第一家的 那么循环到n-1 截至 并且保存一个cmp
第二次循环是不偷第一家的 循环到n截至。然后比较cmp 与 dp [n] 的最大值即可。
文章来源:https://www.toymoban.com/news/detail-605300.html
代码是:
//code
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size()-1;
if(n==1) return max(nums[0],nums[1]);
if(n==0) return nums[0];
int dp[1000]={0};
dp[0]=nums[0];
dp[1]=max(dp[0],nums[1]);
for(int i=2;i<n;i++){
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
int cmp = dp[n-1];
dp[0]=0;
dp[1]=nums[1];
for(int i=2;i<=n;i++){
dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
}
return max(cmp,dp[n]);
}
};
到了这里,关于LeetCode213.House-Robber-II<打家劫舍II>的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!