爬楼梯

解法与斐波那契数列相似，都是基于 f(n) = f(n – 1) + f(n – 2)

1. 暴力递归

工夫复杂度 O(2^n)
空间复杂度 O(n)

（堆栈会溢出）

// 全局变量，示意递归的深度
let depth = 0;

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

2. 备忘录递归

工夫复杂度 O(n)
空间复杂度 O(n)

应用map数组存储计算的后果

function climbStairs(n) {
    let mapData = new Map();
    return myClimbStairs(n, mapData);
}

function myClimbStairs(n, mapData) {
    if (n < 1) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    if (n === 2) {
        return 2;
    }
    // 曾经计算过间接返回
    if (mapData.get(n)) {
        return mapData.get(n);
    }

    let value = climbStairs(n - 1) + climbStairs(n - 2);
    mapData.set(n, value);
    return value;
}

3. 动静布局

工夫复杂度 O(n)
空间复杂度 O(1)

function climbStairs(n) {
    if (n < 1) {
        return 0;
    }
    // base case
    if (n === 1) {
        return 1;
    }
    if (n === 2) {
        return 2;
    }

    // 因为状态转移只和上一次迭代和上上次迭代的后果无关，所以只用两个变量存储，不须要用数组，缩小了空间
    let pre = 1;
    let cur = 2;

    for (let i = 3; i <= n; i++) {
        let sum = pre + cur;
        pre = cur;
        cur = sum;
    }

    return cur;
}