斐波那契是递归思想

[0,1,1,2,3,5,8,13,21,34]

迭代

function fibonacciIterative(n) {
    if(n < 1) return 0
    if(n <=2) return 1
    let fibNMinus2 = 0
    let fibNMinus1 = 1
    let fibN = n
    for(let i=2;i<=n;i++) {
        fibN = fibNMinus1 + fibNMinus2
        fibNMinus2 = fibNMinus1
        fibNMinus1 = fibN
    }
    return fibN
}

递归，容易超出时间限制

递归即调用自己本身

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

对一些算法来说，迭代的解法可能不可用，而且有了尾调用优化，递归的多余消耗甚至可能被消除。

记忆化

类似缓存

var fib = function(N) {
    // 备忘录全初始化为 0
    let memo = new Array(N + 1).fill(0);
    // 进行带备忘录的递归
    return dp(memo, N);
};

// 带着备忘录进行递归
var dp = function(memo, n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
};

还可以用哈希表记录一下算过的

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let map = new Map()
    map.set(0,0)
    map.set(1,1)
    map.set(2,1)
    if(n < 1) return map.get(0)
    if(n <= 2) return 1;
    if(n >= 3) {
        for(let i = 3;i<=n;i++) {
            map.set(i, map.get(i -1)+map.get(i - 2))
        }
        console.log(map)
        return map.get(n)
    }
};

自底向上

啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推

var fib = function(N) {
    if (N === 0) return 0;
    let dp = new Array(N + 1).fill(0);
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (let i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
};