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

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

解答方法分析：

1. 定义一个数组dp，其中dp[i]表示前i块草料能够获得的最高饱腹感。
2. 可以考虑递推关系，对于第i块草料，有两种选择：如果选择吃第i块草料，则前面的状态为dp[i-2]，即前i-块草料能够获得的最高饱腹感。当前的饱腹感为第i块草料的值加上dp[i-2]。 如果选择不吃第i块草料，则前面的状态为dp[i-1]，即前i-1块草料能够获得的最高饱腹感。
3. 取dp[i]的值为这两种选择中的较大值，即max(nums[i] + dp[i-2], dp[i-1])。
4. 所求的答案就是dp[nums.size()-1]。

所用编程语言：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> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
};