LeetCode

70. 爬楼梯

思路

递推，动态规划

F(n)表示爬到第n个台阶时的方案数，有多少种方法可以爬上去。

递归

题解

动态规划

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n === 1) return 1 
    // 下标表示n阶，值为方法数
    const dp = [1, 1]
    for(let i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};

优化，利用滚动数组思想把空间复杂度优化为O(1)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n < 2 ) return 1 
    let dp0 = 1
    let dp1 = 1
    // 不用数组，用两个指针临时存，向右移动
    for(let i = 2; i <= n; i++){
        let temp = dp0
        dp0 = dp1 
        dp1 = dp1 + temp 
    }
    return dp1
};

递归

// 会超时的递归代码
var climbStairs = function(n) {
    function dfs(i) {
        if (i <= 1) { // 递归边界
            return 1;
        }
        return dfs(i - 1) + dfs(i - 2);
    }
    return dfs(n);
};
// 超时~~ 
// 时间：O(2^n)
// 空间：O(n)   栈空间

优化 初始化 memo存状态

var climbStairs = function(n) {
    let memo = Array(n + 1).fill(0)
    function dfs(i) {
        if (i <= 1) { // 递归边界
            return 1;
        }
        // 计算过的不用计算了
        if(memo[i]){
          return memo[i] 
        }
        return memo[i] = dfs(i - 1) + dfs(i - 2);
    }
    return dfs(n);
};

参考

• 灵神-教你一步步思考动态规划：从记忆化搜索到递推