斐波那契数列

• n = n - 1 + n - 2

翻书、走台阶问题

• 共有 n 个台阶，每次只能上 1、2 个台阶，共有多少种方法爬完台阶
• 共有 n 页书，每次只能翻 1、2 页，共有多少种方法翻完全书

// 时间复杂度 O(n²)
function fibonacci(n) {
    if(n === 1) return 1
    if(n === 2) return 2
    if(n > 2) {
        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}
fibonacci(10)

// 时间复杂度 O(n)
function fibonacci2(n) {
    let arr = new Array(n + 1).fill(0)
    arr[1] = 1
    arr[2] = 2
    for(let i = 3; i < n + 1; i++) {
        arr[i] = arr[i - 1] + arr[i - 2] 
    }
    return arr[n]
}
fibonacci2(100)

let cache = {}
function fib(n) {
    if(!(n in cache)) {
        cache[n] = fib_(n)
    }
    return cache[n]
}
function fib_(n) {
    if(n === 1 || n === 2) return n
    return fib(n - 1) + fib(n - 2)
}
fib(100)