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

考察的知识点：动态规划；

解答方法分析：

1. 判断列表长度。如果列表长度为0，返回；如果长度为1，直接返回列表中唯一的元素。
2. 计算链1的最大饱腹感值。创建数组dp1，长度为n+1，初始化为0。数组dp1的每个元素dp1[i]表示以列表中的第i个元素为链1的最后一个节点时最大饱腹感值。特殊情况下，dp1[0] = 0，dp1[1] = nums[0]。从第2个元素开始遍历，计算dp1[i]的值为前两个元素的最大饱腹感值加上第i-1个元素的值。最后的结果为dp1[n-1]，即链1的最大饱腹感值。
3. 计算链2的最大饱腹感值。创建数组dp2，长度为n+1，初始化为0。数组dp2每个元素dp2[i]表示以列表中的第i个元素为链2的最后一个节点时的最大饱腹感值。特殊情况下，dp2[0] = 0，dp2[1] = nums[1]。从第2个元素开始遍历，计算dp2[i]的值为前两个元素的最大饱腹感值加上第i个元素的值。最后的结果为dp2[n-1]，即链2的最大饱腹感值。
4. 返回链1和链2最大饱腹感值中的较大值，即max(max_sum1, max_sum2)。

所用编程语言：C++；

完整编程代码：↓

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