70-爬楼梯.md

70-爬楼梯.md

原题

解法

一：动态规划

这道题就是用来考动态规划的，所以首先就应该使用动态规划来做

const climbStairs = function(n) {
    if (n === 1) {
        return;
    }

    let dp = [];
    dp[1] = 1;
    dp[2] = 2;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i -2];
    }
    return dp[n];
}

复杂度分析

• 时间复杂度O(n)，单循环到 n
• 空间复杂度O(n)，dp数组用了 n 的空间

二：斐波那契

解法一种使用了 dp，核心是 dp[i] = dp[i - 1] + dp[i -2]; 也就是符合斐波那契的规则

Fib(n) = Fib(n - 1) + Fib(n - 2);

使用斐波那契解法为

这种解法是递归，上面动态规划使用的是循环 尾递归的优化[函数最后调用自身可以减少中间变量]

const climbStairs = function(n) {
    if (n === 1) {
        return 1;
    }

    if (n === 2) {
        return 2;
    }

    return climbStairs(n - 2) + climbStairs(n - 1);
}

复杂度分析

• 时间复杂度：O(n)，单循环到 n，需要计算第 n 个斐波那契数
• 空间复杂度: O(1)，使用常量级空间

注意 尾递归优化是单纯的没有使用变量的优化，但是这种没有使用数组或者map缓存之前计算的结果，也会造成很严重的计算浪费， 所以肯定是需要缓存的