题解 | #贪吃牛#

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

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题要求计算牛有多少种不同的方式吃完给定的 n 块草料，每次可以吃 1 块或者 2 块。

思路：

1. 使用动态规划来解决问题。我们可以创建一个长度为 n+1 的数组 dp，其中 dp[i] 表示牛有多少种不同的方式吃完 i 块草料。
2. 初始时，设置 dp[0] = 1 表示牛不吃草料也是一种方式。
3. 状态转移方程：对于 dp[i]，可以从 dp[i-1] 和 dp[i-2] 这两种状态转移得到，因为牛每次可以吃 1 块或者 2 块草料。dp[i] = dp[i-1] + dp[i-2]
4. 最终返回 dp[n] 即为牛吃完 n 块草料的方式总数。

举例说明：例如，给定 n 块草料为 4，按照上述思路计算的方式总数为 5。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param n int整型 表示牛要吃的草料块数
     * @return int整型 表示牛吃完草料的不同方式总数
     */
    int eatGrass(int n) {
        if (n <= 0) return 0; // 如果 n 小于等于 0，则没有任何吃草的方式，直接返回 0
        if (n == 1) return 1; // 如果 n 等于 1，则只有一种吃草的方式，直接返回 1

        vector<int> dp(n + 1, 0); // 创建动态规划数组 dp，长度为 n+1，初始值为 0
        dp[0] = 1; // 牛不吃草也是一种方式，初始化 dp[0] 为 1
        dp[1] = 1; // 只有一块草料时，只有一种吃草的方式，初始化 dp[1] 为 1

        // 计算 dp[i] 的值，表示牛吃完 i 块草料的不同方式总数
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程，dp[i] 可由 dp[i-1] 和 dp[i-2] 转移得到
        }

        return dp[n]; // 返回牛吃完 n 块草料的不同方式总数
    }
};

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