剑指 Offer 10- II. 青蛙跳台阶问题

题目描述：

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

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

示例：

输入：n = 2
输出：2

输入：n = 7
输出：21

输入：n = 0
输出：1

思路：

斐波那契数列：跳1个台阶有一种方法，跳2个台阶可以有两种跳法，而跳3个台阶则就是跳一个台阶和跳2个台阶方法总和，

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
var numWays = function(n) {
    if(n <= 1) return 1;
    if(n == 2) return 2;
    let n1 = 1;
    let n2 = 2;
    let sum = 0;
    for(let i=3;i<=n;i++){
        sum = (n1 + n2) % 1000000007;
        n1 = n2;
        n2 = sum
    }
    return sum;
};