题解 | #牛吃草捆的问题#

1.考察知识点

数组、动态规划

2.编程语言

C++

3.解题思路

典型的动态规划问题，与上楼梯有多少种方式一样

首先定义动态规划数组dp[n];

确定初态dp[0] = 1;dp[1] = 1;dp[2] = 2;

状态转移方程为dp[i] = (dp[i-1] + dp[i-2])%(1000000007)，根据题目要求进行取模运算

最后执行循环，返回结果即可

4.完整代码

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
 */
int countDays(int n ) {
    // write code here
    //动态规划一维数组
    int dp[n+1];
    //初态
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    //循环
    for(int i=3;i<=n;i++)
    {
        //状态转移方程
        dp[i] = (dp[i-1] + dp[i-2])%(1000000007);
    }
    return dp[n];
}