limanting 的个人博客

题目

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

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

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

我的答案

/**
 * @param {number} n
 * @return {number}
 */
var numWays = function (n) {
    if(n<2){
        return 1;
    }
    let prePre=1;
    let pre=1;
    let i=2;
    while(i<n){
        const temp=(prePre+pre)%(1e9+7);
        prePre=pre;
        pre=temp;
        i++;
    }
    return (prePre+pre)%(1e9+7);
};

如果写递归，复杂度是2^n (会重复计算很多次)，其实这就是一个斐波那契数列的解法。