70 爬楼梯

回溯

details

var climbStairs = function (n) {
    let ans = 0;
    backtrack(0);
    return ans;

    function backtrack(start) {
        if (start === n) {
            ans++;
            return;
        }
        if (start > n) {
            return;
        }
        backtrack(start + 1);
        backtrack(start + 2);
    }
};

时间复杂度: 暴力解法的时间复杂度为 $O(2^n)$。这是因为每次递归调用时，都会产生两个分支$（n-1 和 n-2）$，这导致了指数级的增长。

空间复杂度: 空间复杂度为 $O(n)$，这是因为递归的深度最深为 n，函数调用栈的大小也为 n。

记忆化

var climbStairs = function (n) {
    let ans = 0;
    let map = new Map();
    backtrack(0);
    return ans;

    function backtrack(start) {
        if (start === n) {
            ans++;
            return;
        }
        if (start > n) {
            return;
        }
        if (map.has(start)) {
            return map.get(start);
        }
        let result = backtrack(start + 1) + backtrack(start + 2);
        map.set(start, result);
    }
};

递归

details

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

时间复杂度: 暴力解法的时间复杂度为 $O(2^n)$。这是因为每次递归调用时，都会产生两个分支$（n-1 和 n-2）$，这导致了指数级的增长。

空间复杂度: 空间复杂度为 $O(n)$，这是因为递归的深度最深为 $n$，函数调用栈的大小也为 $n$。

记忆化递归

var climbStairs = function (n) {
    let memo = new Array(n + 1).fill(-1);
    return climb(n);

    function climb(i) {
        if (i <= 1) return 1;
        if (memo[i] !== -1) return memo[i];
        memo[i] = climb(i - 1) + climb(i - 2);
        return memo[i];
    }
};

迭代

动态规划 使用动态规划可以进一步优化，将递归改为迭代

details

var climbStairs = function (n) {
    if (n <= 1) return 1;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

动态规划（优化空间复杂度）

var climbStairs = function (n) {
    if (n <= 1) return 1;
    let prev1 = 1;
    prev2 = 1;

    for (let i = 2; i <= n; i++) {
        let cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
};