青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个问题与斐波那契数列问题基本相同

假设有10个台阶需要跳，那么到达第10阶台阶的步骤只有两种即step(9)和step(8)两种,两种方法相互独立，即到达第10阶台阶的路线数量等于到达第9阶台阶的数量加上到达第8阶台阶的数量，即step[10]=step[9]+step[8]

step[N]=step[N-1]+step[N-2],其中（N>=3）

计算时可采用自底向上的方式，减少计算量，节省内存

class Solution {
    public int numWays(int n) {
        if (n < 2) return 1;
        if (n == 2) return 2;
        int first = 1, second = 2;
        int ways = 0;
        for (int i = 3; i <= n; i++) {
            ways = (first + second)%1000000007;
            first = second;
            second = ways;
        }
        return ways;
    }
}

赏

谢谢你请我吃糖果

微信