题解 | 贪吃牛

语言： C++

知识点： 动态规划

分析： 本题是经典的爬楼梯问题类型，使用动态规划方法解题：定义dp数组表示吃完当前下标个数的草料共有多少种吃法（例如dp[2]存储的是吃完两块草料有多少种方法，易得dp[2] = 2即一次吃两块或两次各吃一块共2种吃法）。思考从第三块草料来看，吃完的方法数为 吃完一块草料的方法数然后再1次吃两块草料 以及 吃完两块草料的方法数然后再1次吃一块草料（即只考虑当前最后一次吃草料的块数（两种情况吃一块和吃两块），然后将本次吃草料的次数1加上去掉本次吃的块数后存在的总吃法次数求和，即为吃完当前草料数所存在的总次数），由此可推广得到状态转移方程为：dp[n] = dp[n - 1] + dp[n - 2]（斐波那契数列）。由于下标0时没有实际意义，因此初始化时只需初始dp[1] = 1, dp[2] = 2即可。最终返回dp[n]即为吃完n块草料的总吃法数。

代码实现：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int eatGrass(int n) {
        vector<int> dp(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];
    }
};

优化： 由于遍历过程中状态只与前两个状态有关，因此可以只定义两个变量存储前两种状态，实现空间上的优化。

优化后代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int eatGrass(int n) {
        if(n == 1) // 需单独判断只有1块草料时的情况
        {
            return 1;
        }
        int dp1 = 1, dp2 = 2; // 只使用两个变量存储前两种状态即可
        for(int i = 3; i <= n; i++)
        {
            int tmp = dp2;
            dp2 += dp1; // 此处即为状态转移方程
            dp1 = tmp;
        }
        return dp2;
    }
};