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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int eatGrass (int[] nums) {
        // write code here
        int n = nums.length;
        if (n == 1)
            return nums[0];
        else if (n == 2)
            return Math.max(nums[0], nums[1]);
        else if (n == 3)
            return Math.max(nums[0], Math.max(nums[1], nums[2]));

        // dp1数组记录不吃最后一根草的最大值
        int[] dp1 = new int[n - 1];
        dp1[0] = nums[0];
        dp1[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n - 1; i++) {
            // 在当前位置有两种选择：吃或者不吃
            // 如果吃，则最大值为前两根草的最大值加上当前位置的草量
            // 如果不吃，则最大值为前一根草的最大值
            dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
        }

        // dp2数组记录吃最后一根草的最大值
        int[] dp2 = new int[n];
        dp2[1] = nums[1];
        dp2[2] = Math.max(nums[1], nums[2]);

        for (int i = 3; i < n; i++) {
            // 在当前位置有两种选择：吃或者不吃
            // 如果吃，则最大值为前两根草的最大值加上当前位置的草量
            // 如果不吃，则最大值为前一根草的最大值
            dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
        }

        // 返回dp1数组中不吃最后一根草的最大值和dp2数组中吃最后一根草的最大值的较大值
        return Math.max(dp1[n - 2], dp2[n - 1]);
    }
}

这段代码使用的编程语言是Java。

该题考察的知识点是动态规划。动态规划是一种常见的算法设计和优化方法，通常用于解决具有重叠子问题和最优子结构性质的问题。通过将问题分解为子问题并保存子问题的解，可以避免重复计算，从而提高算法的效率。

这段代码的解释如下：

1. 根据输入的数组长度判断特殊情况：当长度为1时，直接返回数组中唯一的元素；当长度为2时，返回两个元素中较大的一个；当长度为3时，返回三个元素中最大的一个。
2. 创建两个数组 dp1 和 dp2，分别用来记录不吃最后一根草和吃最后一根草的最大值。
3. 对于 dp1 数组，从第三个位置开始遍历，每个位置上的最大值是在不吃当前位置的草和吃当前位置的草中选择较大的那个，并将该最大值保存在 dp1 数组中。
4. 对于 dp2 数组，从第四个位置开始遍历，每个位置上的最大值也是在不吃当前位置的草和吃当前位置的草中选择较大的那个，并将该最大值保存在 dp2 数组中。
5. 从 dp1 数组的倒数第二个位置和 dp2 数组的最后一个位置中选择较大的值作为结果，并返回。

这段代码利用动态规划的思想，通过保存子问题的解避免了重复计算，找到了吃或不吃每根草时的最优选择，最终得到了吃草的最大值。