京东 上台阶 动态规划

题目描述

有一楼梯共m级,刚开始时你在第一级,若每次只能跨上一级或者二级,要走上m级,共有多少走法?注:规定从一级到一级有0种走法。

给定一个正整数int n,请返回一个数,代表上楼的方式数。保证n小于等于100。为了防止溢出,请返回结果Mod 1000000007的值。

测试样例:

3
返回:2
class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        #define mod 1000000007
        int maxn = 1e2+5;
        int dp[maxn];
        dp[1]=0;
        dp[2]=1;
        dp[3]=2;
        for(int i=4;i<=n;++i)
        {
            dp[i]=(dp[i-1]+dp[i-2])%mod;
        }
        return dp[n];
    }
};
Last modification:January 11th, 2020 at 10:42 pm
如果觉得我的文章对你有用,请随意赞赏