本文共 410 字，大约阅读时间需要 1 分钟。

题目描述

    有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。

代码实现

class GoUpstairs {public:    int countWays(int n) {//第一次走1台阶,剩下n-1阶,第一次走2台阶,剩下n-2阶        int *dp = new int[n+1];//所以状态转移方程为 dp[i] = dp[i-1] +dp[i-2];        dp[0] = dp[1] = 1;        for (int i=2; i<=n; ++i) {            dp[i] = (dp[i-1]+dp[i-2])%1000000007;        }        return dp[n];    }};

转载地址：http://yehji.baihongyu.com/