【动态规划】打家劫舍Ⅱ

题目链接：https://leetcode.cn/problems/house-robber-ii/description/

classSolution{public:introb(vector<int>&nums){intn=nums.size();// 两种情况下的最大值returnmax(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));}introb1(vector<int>&nums,intleft,intright){/*打家劫舍Ⅰ里的逻辑*/if(left>right)return0;// 1. 创建dp表intn=nums.size();vector<int>f(n);autog=f;// 2. 初始化f[left]=nums[left];// 3. 填表for(inti=left+1;i<=right;++i){f[i]=nums[i]+g[i-1];g[i]=max(f[i-1],g[i-1]);}// 4. 返回值returnmax(f[right],g[right]);}};