【力扣-每日一题】213. 打家劫舍 II

class Solution {
public:
    int getMax(int n,vector<int> &nums){
        int a=0,b=nums[n],c=0;
        for(int i=n+1;i<nums.size()+n-1;i++){   //size+n-1,为0时，第一个可以偷，最后一个不能偷size-1；n为1时，最后一个可偷，计算到nums.size()
            if(i-2<0)       
                c=max(b,nums[i]);
            else 
              c=max(a+nums[i],b);  //当前值来自前一项（不偷）或前两项（偷）
            a=b;    //滚动
            b=c;
        }
    
    return b;
    }
    int rob(vector<int>& nums) {
        if(nums.size()==1)
            return nums[0]; //只有一家时，直接返回
        else return max(getMax(0,nums),getMax(1,nums)); //第一个偷与不偷分开考虑，解环
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21