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

一、知识点：

数组、遍历、循环

二、文字分析：

• 定义一个长度为n的数组dp，其中dp[i]表示牛吃到第i块草时得到的最高饱腹感。
• 初始状态：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
• 状态转移方程：dp[i] = max(dp[i-1], dp[i-2]+nums[i])。
• 最终结果为dp[n-1]。

时间复杂度：

• 初始化dp数组需要O(n)的时间复杂度。
• 循环遍历dp数组更新每个元素的值，需要O(n)的时间复杂度。

所以整体上，算法的时间复杂度为O(n)。

空间复杂度：

• 需要一个长度为n的dp数组来保存中间状态，因此需要O(n)的空间复杂度来存储中间结果。

综上所述，算法的空间复杂度为O(n)。

三、编程语言：

java

四、正确代码：

import java.util.*;

public class Solution {
    public int eatGrass(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

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

        return dp[n - 1];
    }
}