题解 | #贪吃牛#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    public int eatGrass (int n) {
        // write code here
        if (n <= 0) {
            return 0;
        }

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

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

知识点：

1. 动态规划：一种通过将问题分解成子问题，并存储子问题的解来解决问题的方法。
2. 斐波那契数列：每个数是前两个数之和的数列。

解题思路：

使用一个动态规划数组 dp 来存储每个数对应的吃草方式数量。初始条件为 dp[1] = 1 和 dp[2] = 2，因为在只有一块和两块草料时，有固定的吃法。然后，我们从 i = 3 开始，逐步计算每个数对应的吃草方式数量，即 dp[i] = dp[i - 1] + dp[i - 2]。最终，返回 dp[n] 即为牛吃完 n 块草料的不同方式数量。