爬楼梯

/**
 * 时间复杂度O(2^n)
 */
const climbStairsByRecursion = (n) => {
    if(n === 1) return 1
    if(n === 2) return 2
    return climbStairsByRecursion(n - 1) + climbStairsByRecursion(n - 2)
}

/**
 * 动态规划
 * 时间复杂度O(n)
 * 空间复杂度O(n)
 */
const climbStairsByDynamic = (n) => {
    const arr = [0,1,2]
    if(n < 3){
        return arr[n]
    }
    for(let i = 3; i <= n; i++){
        arr[i] = arr[i - 1] + arr[i - 2]
    }
    return arr[n]
}

/**
 * 斐波那契
 * 时间复杂度O(n)
 * 空间复杂度O(1)
 */
const climbStairsByFibonacci = (n) => {
    let x = 1,y = 1
    while(--n > 0){
        y = x + y
        x = y - x
    }
    return y
}