题解 | #不能连续吃草的牛II#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int f(vector<int>&nums,int left,int right){
        int n=nums.size();
        vector<int> dp(n);
        dp[left]=nums[left];
        dp[left+1]=max(dp[left],nums[left+1]);
        for(int i=left+2;i<=right;++i){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[right];
    }
    int eatGrass(vector<int>& nums) {
        // write code here
        int n=nums.size();
        if(n==0){
            return 0;
        }
        if(n==1){
            return nums[0];
        }
        return max(nums[0]+f(nums,2,n-2),f(nums,1,n-1));
    }
};

由于是环形的数据，所以第一个值分为取和不取两种情况：

1. 取：则第二个和最后一个不能取，即求从2到n-2的最大情况，然后加上第一个的值即可；
2. 不取：则求从第二个到最后一个的最大情况即可。

实现方法就是先定义一个函数，实现从数组的某一位置开始到另一位置结尾计算最大情况的值，dp【i】表示第i个位置的最大吃草数，状态转移方程表示取（前一个dp）与（当前值与前两个位置的dp值的和）的较大值，返回的是到达最后一个位置的时候的最大吃草数。

两种情况调用此函数，注意左右边界，然后取较大值即可。