70. 爬楼梯

leetCode-70. 爬楼梯

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

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

示例一：

输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶

1. 1阶 + 1阶
2. 2阶

示例二：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶

1. 1阶 + 1阶 + 1阶
2. 1阶 + 2阶
3. 2阶 + 1阶

解答答案

第一种：递归

使用递归，只需要关注最后两步的方案，需要通过一个字典记录缓存。时间复杂度O(n!)，空间复杂度O(n)

const cache = {}
function climbStairs(n: number): number {
    if (cache[n]) {
        return cache[n];
    }
    if (n === 1 || n === 2) {
        cache[n] = n;
        return n
    };
    const result = climbStairs(n - 1) + climbStairs(n - 2);
    cache[n] = result;
    return result;
};

第二种：递归改迭代

递归改迭代，用一个数组承接结果，时间复杂度O(n)，空间复杂度O(n)

function climbStairs(n: number): number {
    const arr = [];
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 2;
    for(let i = 3; i <= n; i++) {
        arr.push(arr[i - 1] + arr[i - 2])
    }
    return arr[n];
};

第三种：迭代+空间压缩

迭代然后进行空间压缩法，用两个指针代替数组，时间复杂度O(n)，空间复杂度O(1)

function climbStairs(n: number): number {
    if (n === 1 || n === 2) return n;
    let a = 1; // 前两
    let b = 2; // 前一
    let result = 0;
    for(let i = 3; i <= n; i++) {
        result = a + b;
        a = b;
        b = result;
    }
    return result;
};