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

题目考察的知识点

从题目考察的知识点来看，本题考察了动态规划和环形数组的处理。

题目解答方法的文字分析

题目要求找到一种安排牛吃草的顺序，使牛在不连续吃相邻的草料的情况下获得最高的饱腹感。解决这个问题的思路是利用动态规划，分为不选取第一块草料和不选取最后一块草料两种情况。

创建两个动态规划数组dp1和dp2，其中dp1[i]表示不选取第一块草料时前i块草料的最大饱腹感，dp2[i]表示不选取最后一块草料时前i块草料的最大饱腹感。为了解决环形数组的问题，我们需要遍历两次，分别计算dp1和dp2数组。

具体的状态转移方程为：

• 对于dp1数组，dp1[i] = max(dp1[i-1], dp1[i-2] + nums[i])，不选取第一块草料时，当前最大饱腹感等于前一块草料的最大饱腹感或者前两块草料的最大饱腹感加上当前草料的饱腹感的最大值。
• 对于dp2数组，dp2[i] = max(dp2[i-1], dp2[i-2] + nums[i])，不选取最后一块草料时，当前最大饱腹感等于前一块草料的最大饱腹感或者前两块草料的最大饱腹感加上当前草料的饱腹感的最大值。

最终的结果是在dp1和dp2数组的最后一个元素中选择较大的值作为最高饱腹感。

本题解析所用的编程语言

本题解析所用的编程语言是JavaScript。

完整且正确的编程代码

function eatGrass(nums) {
  const n = nums.length;

  if (n === 0) {
    return 0;
  }

  if (n === 1) {
    return nums[0];
  }

  // 计算不选第一块草料的情况
  const dp1 = new Array(n).fill(0);
  dp1[0] = 0;
  dp1[1] = nums[1];
  for (let i = 2; i < n; i++) {
    dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
  }

  // 计算不选最后一块草料的情况
  const dp2 = new Array(n).fill(0);
  dp2[0] = nums[0];
  dp2[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n - 1; i++) {
    dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
  }

  // 取dp1和dp2的最大值作为结果
  return Math.max(dp1[n - 1], dp2[n - 2]);
}

// 示例：
console.log(eatGrass([1, 2, 3, 1])); // 输出：4，选择第1、3块草料获得最高饱腹感
console.log(eatGrass([2, 7, 9, 3, 1])); // 输出：10，选择第2、4、5块草料获得最高饱腹感