https://jackniu81.github.io/2021/04/18/Algorithm-Fibonacci-numbers/

1. 斐波那契數列

斐波那契數列：0, 1, 1, 2, 3, 5, 8, 13 ... ...

通常用 F(n) 表示，形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

敏捷開發時，我們估算Story Point，通常就是使用斐波那契數列。

2. 解題思路

2.1. 遞歸

F(n) = F(n - 1) + F(n - 2)， 很簡單，就不談了。

2.2. 動態規劃

動態規劃的思想是，記錄中間計算結果，計算后面相時，根據前面保存的結果直接計算，避免重復計算。

3. Javascript 實現

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n===0)
        return 0;
    if(n===1)
        return 1;

    let arr = [0,1]
    for(let i=2;i<=n;i++){
        arr[i] = arr[i-1] + arr[i-2];
    }
    return arr[n];
};

還可以進一步優化，當前使用數組記錄以及計算過的F(n)，由于F(n) = F(n - 1) + F(n - 2)，實際只需要記錄最近的2個值即可，不需要使用數組記錄全部數據。