题解 | #贪吃牛#

知识点

动态规划

分析

如果N=1，共有1种方案；

如果N=2，共有2种方案；

如果N=3，可以吃1，剩2，也可以吃2，剩下1，所以共有2+1=3种方案；

如果N=4，则吃1，剩3，也可以吃2，剩2，共有3+2=5种方案。

则f[i] = f[i - 1] + f[i - 2]

那么使用动态规划就可以解决了。

编程语言

C++

完整代码

int eatGrass(int n) {
        int f[10010] = {0};
        f[1] = 1; f[2] = 2;
        for (int i = 3; i <= n; i++){
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }