大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

  • 动态规划
  • 环形问题的处理

题目解答方法的文字分析

这道题目考察了动态规划的应用，以及如何处理环形问题。我们需要计算一个特殊的牛在不引起食欲降低的情况下，能够吃到的草得到的最高饱腹感。

解题思路如下：

  1. 由于草料是围成一个环的，我们可以将环拆成两部分，分别计算每部分的最高饱腹感。
  2. 拆分环的方法有两种：一种是特殊牛不吃第一块草料，另一种是特殊牛不吃最后一块草料。
  3. 对于线性问题的最高饱腹感计算，我们使用动态规划。定义 dp[i] 表示前 i 块草料能够让牛吃到的草得到的最高饱腹感。
  4. 推导状态转移方程：若牛不吃第 i 块草料，则 dp[i] = dp[i-1]；若牛吃第 i 块草料，则 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
  5. 最后取拆分环两种情况的最大值作为结果返回。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector，表示每块草的饱腹感
     * @return int整型，表示能够让牛吃到的草得到的最高饱腹感
     */
    int eatGrass(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return nums[0]; // 特殊情况处理：只有一块草的时候直接返回该块草的饱腹感
        }

        // 拆分环，计算不吃第一块草料和不吃最后一块草料的情况
        int max1 = eatGrassHelper(nums, 0, n - 1);
        int max2 = eatGrassHelper(nums, 1, n);

        // 取两种情况的最大值
        return max(max1, max2);
    }

    // 计算线性问题的最高饱腹感
    int eatGrassHelper(vector<int>& nums, int start, int end) {
        int n = end - start;
        if (n == 0) {
            return 0;
        }

        vector<int> dp(n, 0); // dp数组，dp[i]表示前i块草料能够让牛吃到的草得到的最高饱腹感
        dp[0] = nums[start]; // 初始化dp数组的第一个元素

        for (int i = 1; i < n; ++i) {
            // 若牛不吃第i块草，则前i块草料的最高饱腹感与前i-1块草料的最高饱腹感相同
            // 若牛吃第i块草，则前i块草料的最高饱腹感为前i-2块草料的最高饱腹感加上当前第i块草的饱腹感nums[start + i]
            dp[i] = max(dp[i - 1], (i >= 2 ? dp[i - 2] : 0) + nums[start + i]);
        }

        return dp[n - 1]; // 返回dp数组中的最后一个元素，即为牛吃到的草得到的最高饱腹感
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！