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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    
    int eatGrass(vector<int>& nums) {
        // write code here
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);
        vector<int> dp(nums.size());
        int ansMax = 0;
        // 第一个位置吃，最后一个位置不吃
        dp[0] = nums[0];
        dp[1] = max(dp[0], nums[1]);   // 这里需要注意，第一个位置吃不吃影响的是遍历的后面的位置
        // dp表示的是当前可以获得的最大的饱腹感，如果为[1, 3, 4,..], 那么dp[1]就为3,此时就表示吃第二个位置
        // 不吃第一个位置
        for (int i = 2; i < nums.size()-1; i++) {
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        // 不吃第一个位置
        vector<int> dp1(nums.size());
        dp1[0] = 0;
        dp1[1] = nums[1];
        for (int i = 2; i < nums.size(); i++) {
            dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i]);
        }

        return max(dp[nums.size()-2], dp1[nums.size()-1]);
    }
};