一、知识点

动态规划、斐波那契数列

二、文字分析

1.定义数组元素的含义

定义数组dp[i]含义，表示这头牛吃完这i块草料有dp[i]种不同的方式。

2.确定决策并写出状态转移方程

假设我们已知吃完1~n-1块草料的不同的方式，如何求出吃完n块草料的方式？

由于一头牛一次只能吃1块或者2块草料。所以吃n块草料由两种方法得来，即吃完n-1块草料后在吃1块草料或吃完n-2块草料后吃两块草料。

得出状态转移方程：dp[n] = dp[n-1] + dp[n-2]

3.确定边界值

当n = 1或n = 2时，为状态转移方程的边界值。容易得出dp[1] = 1,dp[2] = 2。

三、编程语言

c++

四、编程代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int eatGrass(int n) {
        // write code here
        vector<int>dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
        return dp[n];
    }
};