首页 > 其他 > 详细

青蛙跳台阶

时间:2020-07-19 00:17:31      阅读:51      评论:0      收藏:0      [点我收藏+]

青蛙跳台阶

解法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 取模),对应知识点传送门 >>>

青蛙跳台阶

原文:https://www.cnblogs.com/hjj2ldq/p/13338058.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!