青蛙跳台阶

青蛙跳台阶

解法1:

var numWays = function(n) {
    var memo = [1,1,2]
    var fn = function(m){
        if(memo[m]){
            return memo[m]
        }
        return memo[m] = (fn(m - 1) +fn(m-2)) % (1e9+7);
    }
    return fn(n)
};

优化点: 创建记忆数组,免去重复计算,尤其在n很大的时候会超时.
提示: 此方法跟后两者其实都比较像,只不过把循环相加化作斐波那契数列解法

解法2:

var numWays = function (n) {
    if (n <= 1) return 1;
    let first = 1; // 0 级台阶
    let second = 1; // 1 级台阶
    for (let i = 2; i <= n; i++) { // 2 级台阶起跳
        let tmp = first;
        first = second;
        second = (tmp + first) % 1000000007;
    }
    return second;
};
// 1 1 2 3 5 8 13 21 34 55 89
分析: 有些解法可能会设三个变量,如 1,1,2起步.对照上行分析一下,其实两个指针就够用了.

解法3:

var numWays = function(n) {
    if (n <= 1) return 1;
    let dp = [1, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = (dp[i-1] + dp[i-2])%1000000007;
    }
    return dp[n];
};
分析: 对比解法2,该方法空间复杂度为 O(n)

总结: 1 记忆优化 2 大数处理 (采用对1e9 + 7 取模),对应知识点传送门 >>>