Skip to content

LeetCode

70. 爬楼梯

image.png

思路

递推,动态规划

image.png

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

image.png

递归

image.pngimage.png

题解

动态规划

typescript
/**
 * @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)

typescript
/**
 * @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
};

递归

typescript
// 会超时的递归代码
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存状态

typescript
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);
};

参考