打家劫舍 和 打家劫舍 II

打家劫舍 和 打家劫舍 II

打家劫舍

代码如下（示例）：

class Solution{public:introb(vector<int>&nums){// 动态规划滚动数组空间优化if(nums.size()==0)return0;intn=nums.size();intbuy=nums[0],nobuy=0;for(inti=2;i<=n;i++){intcurrentbuy=nobuy+nums[i-1];intcurrentnobuy=max(buy,nobuy);buy=currentbuy;nobuy=currentnobuy;}returnmax(buy,nobuy);}};

打家劫舍 II

代码如下（示例）：

class Solution{public:introb(vector<int>&nums){intn=nums.size();returnmax(nums[0]+robs(nums,2,n-2),robs(nums,1,n-1));}introbs(vector<int>nums,intleft,intright){if(left>right)return0;intn=nums.size();vector<int>f(n);vector<int>g(n);f[left]=nums[left],g[left]=0;for(inti=left+1;i<=right;i++){f[i]=g[i-1]+nums[i];g[i]=max(f[i-1],g[i-1]);}returnmax(f[right],g[right]);}};

总结

这篇文章是作者搜集大量面经和资料这里出来的。感谢你的支持
作者wkm是一名中国矿业大学(北京) 大一的新生，希望得到你的关注
如果可以的话，记得一键三联！