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

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

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题要求我们在不引起特殊牛食欲降低的情况下，计算能让牛吃到的草得到的最高饱腹感。

思路：我们可以使用动态规划来解决这个问题。定义一个一维 dp 数组，其中 dp[i] 表示前 i 块草料能够让牛吃到的草得到的最高饱腹感。

推导状态转移方程：

1. 若牛不吃第 i 块草，则 dp[i] = dp[i-1]，表示前 i 块草料的最高饱腹感与前 i-1 块草料的最高饱腹感相同。
2. 若牛吃第 i 块草，则 dp[i] = dp[i-2] + nums[i]，表示前 i 块草料的最高饱腹感为前 i-2 块草料的最高饱腹感加上当前第 i 块草的饱腹感 nums[i]。

最后，我们只需要返回 dp 数组中的最后一个元素 dp[n-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;
        }

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

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

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

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