题目描述

一串数，构成环。每次取一个，不能取相邻的，要求取得最大和。

思路

拆成两个一维的线性问题，偷第0个即 [0,n-1]，反之[1,n]，返回两者较大的那个。

下面提供四种思路，复杂度O(n)

//朴素dfs
struct robRes{
    int robNow,notRob;
};

class Solution {
public:
    //从小到大逐个考察偷或不偷构成一棵二叉树
    robRes dfs(vector<int>& nums,int start,int end){
        if(start==end) return {0,0};
        robRes son=dfs(nums,start+1,end);
        int robnow=nums[start]+son.notRob;
        int notrob=max(son.notRob,son.robNow);
        return {robnow,notrob};
    }


    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return nums[0];
        robRes ans=dfs(nums,0,n-1);
        int a=max(ans.robNow,ans.notRob);
        robRes ans1=dfs(nums,1,n);
        int b=max(ans1.robNow,ans1.notRob);

        return max(a,b);
    }
};


//树状(dp)数组

class Solution {

    int f[103][2];//fi0 第i家没被偷，fi1被偷了
public:

    void dfs(vector<int>& nums,int start,int end){
        if(start==end) return ;
        dfs(nums,start+1,end);
        f[start][1]=nums[start]+f[start+1][0];
        f[start][0]=max(f[start+1][0],f[start+1][1]);
    }


    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return nums[0];
        dfs(nums,0,n-1);

        int a=max(f[0][0],f[0][1]);

        dfs(nums,1,n);
        int b=max(f[1][0],f[1][1]);

        return max(a,b);
    }
};

//状态机角度——y总

class Solution {
public:
    int f[103][2];//fi0 第i家没被偷，fi1被偷了

    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return nums[0];

        //偷nums[0]
        f[0][0] = -INF, f[0][1] = nums[0];
        for (int i = 1; i < n; i ++ ) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        int res = f[n - 1][0];

        //不偷nums[0]
        f[0][0] = 0, f[0][1] = -INF;
        for (int i = 1; i < n; i ++ ) {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        return max(res, max(f[n - 1][0], f[n - 1][1]));
    }

};

//闫氏dp 化整为零

class Solution {
public:
    int f[103];//fi 前i家偷完后的最大值
    int rob(vector<int>& nums,int start,int end){
        /*
        * f[i]=max(f[i-1],f[i-2]+a[i])
        * let now=fi,pre=f[i-1]
        * now=max(now,pre+ai)
        */
        int now=0,pre=0;
        for(int i=start;i<end;i++){
            int t=max(now,pre+nums[i]);
            pre=now;
            now=t;
        }
        return now;
    }

    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return nums[0];

        int a=rob(nums,0,n-1);
        int b=rob(nums,1,n);

        return max(a,b);
    }
};