爬楼梯

解法与斐波那契数列相似，都是基于 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;}