70. Climbing Stairs

source: https://leetcode.com/problems/climbing-stairs/

Question

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

暴力法

function climbStairs(n: number): number {
    const steps = [1, 2];
    let ret = 0;
    const climb = (lastN: number) => {
        if (lastN === n) {
            ret += 1;
            return;
        }
        if (lastN > n) {
            return;
        }
        steps.forEach(step => climb(lastN + step));
    };
    climb(0);
    return ret;
};

这种解法比较简单容易想到，缺点是有很多重复计算，在leetcode上的test cases是会超时的。

递归

需要归纳一下规律：

• 1. 爬1级台阶，1种方法
• 2. 爬2级台阶，2种方法
• 3. 爬3级台阶，是: 爬1级台阶的结果 + 爬2级台阶的结果，因为在这两种情况的基础上，+1和+2就可以得到爬3级台阶的结果
• ...
• n. 爬n级台阶，f(n) = f(n - 1) + f(n - 2)

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

这种情况下还是超时，和无缓存的斐波那契数列一样，我们为他加一个缓存。

function climbStairs(n: number): number {
    const cache = {};
    const calc = num => {
        if (num === 0) return 0;
        if (num === 1) return 1;
        if (num === 2) return 2;
        const a = num - 1;
        const b = num - 2;
        if (!cache[a]) cache[a] = calc(a);
        if (!cache[b]) cache[b] = calc(b);
        return cache[a] + cache[b];
    };
    return calc(n);
};

动态规划

在缓存的基础，可以比较容易的推出dp版本，这里的dp数组，其实就充当了缓存的角色。

function climbStairs(n: number): number {
    const steps = [1, 2];
    const dp = new Array(n + 1).fill(1);
    for (let i = 2; i <= n; i++) {
        dp[i] = steps.reduce((acc, crr) => acc + dp[i - crr], 0);
    }
    return dp[n];
};

总结

这道题的核心，或者说所有dp题目的核心，还是要推出状态转变公式，这样的话无论是加缓存还是用dp，都是可以的。