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

知识点：

动态规划

环形

分析：

环状排列意味着第一块草料和最后一块草料中只能选择一个吃，因此可以把此环状排列化为两个单排排列子问题

在不吃第一块草料的情况下，最高饱腹感是p1；

在不吃最后一块草料的情况下，最高饱腹感是p2。

最高饱腹感： 为以上两种情况的较大值，即 max(p1,p2)。

编程语言：

C++

完整代码：

    int f[1010];
    int g[1010];
    int eat(vector<int>& nums,int st,int ed,int* f) {
        if(nums.size() <= 1) return nums.size();
        f[st] = nums[st];
        f[st + 1] = max(nums[st + 1],nums[st + 2]);
        for(int i = st+ 2;i<ed;i++){
            f[i] = max(f[i-1],f[i-2] + nums[i]);
        }
        return f[ed - 1];
    }
    int eatGrass(vector<int>& nums) {
        return max(eat(nums, 0, nums.size() - 1, f),eat(nums, 1, nums.size(), g));
    }