题目链接

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解法1 暴力递归和记忆化递归

思路

这本质上就是一个斐波那契数列，所以当 n 走到只有 1 个台阶的时候，只有一种解法。

然后递归去处理。到达 n 这个台阶，有两种方法，要么是走 1 步，要么是走 2 步，所以返回结果是 (n - 1) + (n - 2)。

但是这个方法存在大量的计算，所以无法通过题解。如果这个解法要想通过题解，必须要保存已经计算过的步数，下面给出两种方法。

代码

朴素计算

function climbStairs(n: number): number {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
};

memo缓存

function climbStairs(n: number): number {
    const memo = new Array(n + 1).fill(-1); // -1 代表未计算
    memo[0] = 1;
    memo[1] = 1;

    function dfs(i: number): number {
        if (memo[i] !== -1) return memo[i];
        memo[i] = dfs(i - 1) + dfs(i - 2);
        return memo[i];
    }

    return dfs(n);
}

时空复杂度

时间复杂度：朴素 O(2^n)，记忆化O(n)

空间复杂度：朴素 O(n)，记忆化O(n)

解法2 动态规划

思路

其实上面已经将问题分解成了子问题，到达这个台阶只有两种方法，要么 n - 1，要么 n - 2。

所以其实只需要两个变量就可计算完毕当前台阶，即 prev 和 cur 。当前台阶就是 prev + cur ，然后再更新 prev 和 cur。

代码

function climbStairs(n: number): number {
    if (n <= 1) return 1;
    let prev = 1;
    let cur = 1;
    for (let i = 2; i <= n; i++) {
        const temp = prev + cur;
        prev = cur;
        cur = temp;
    }

    return cur;
}

时空复杂度

时间复杂度：O(n)

空间复杂度：O(1)