II. 青蛙跳台阶问题

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

分析

设 dp(i) 为 跳上 i 台阶的跳法

dp(i) = dp(i-1) + dp(i-2)

• dp(0) = 1
• dp(1) = 1
• dp(2) = 2

这道题本质上跟菲波那数列是一样的，只是，初始值不同。

代码

var numWays = function(n) {
  let n1 = 1,n2=2,sum=0;
  for(let i=0;i<n;i++){
    sum  = (n1+n2)%1000000007
    n1 = n2
    n2 = sum
  }
  return n1
};