SOURCE

// 递推
// function fib(n) {
//     const arr = [];
//     arr[0] = 0;
//     arr[1] = 1;
//     for (i = 2; i <= n; i++) {
//         arr[i] = arr[i - 1] + arr[i - 2];
//     }
//     return arr[n];
// }

// 缓存已算出的数据
const memo = {}
function fib(n) {
    if (n < 2) return n;
    if (!memo[n]) {
        memo[n] = fib(n - 1) + fib(n - 2);
    };
    return memo[n];
}
console.log(fib(100))
//  0 1 1 2 3 5 8 13...