從最簡單的斐波那契數列來學習動態規劃（JavaScript版本）
前言
斐波那契數列是一個很經典的問題，雖然它很簡單，但是在優化求解它的時候可以延伸出很多實用的優化算法。
它的概念很簡單，來看一下 LeetCode 真題里對他的定義：
斐波那契數，通常用 F(n) 表示，形成的序列稱為斐波那契數列。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N，計算 F(N)。
先大概預覽一下斐波那契數列的樣子：
- 1、1、2、3、5、8、13、21、34
青銅時代 - 遞歸求解。
在本文中，下面出現的 fib(n) 代表對于 n 的求解。
有了定義以后，對于這個問題我們第一直覺就是可以用「遞歸」來解，思路也很簡單，只需要定義好初始狀態，也就是 fib(1) = 1，fib(2) = 1，那么假設要求 fib(3) 只需要去求 fib(2) + fib(1) 即可，以此類推。
大概在 fib(50) 的時候，在我的筆記本上跑了 123.167 秒，再往后就更加不敢想象了。由于大量的遞歸調用加上不斷的重復計算，導致這個算法的速度慢到不可接受。
白銀時代 - 備忘錄解法
青銅的解法由于有大量的重復計算，
比如 fib(3) 會計算 fib(2) + fib(1)，
而 fib(2) 又會計算 fib(1) + fib(0)。
這個 fib(1) 就是完全重復的計算，不應該為它再遞歸調用一次，而是應該在第一次求解除它了以后，就把他“記憶”下來。
把已經求得的解放在 Map 里，下次直接取，而不去重復結算。
這里用 iife 函數形成一個閉包，保留了 memo 這個私有變量，這是一個小技巧。
此時對于 fib(50) 的計算速度來到了 0.096 秒，在 50 這個小數量級的情況下就比青銅解法快了 1200 倍。
有一部分說算法無用論的人，持有的觀點是隨著硬件的進步這些差異都會被抹平，那我期待著硬件進步 1000 倍的那一天吧。
黃金時代 - 動態規劃
看似上面的備忘錄解法已經很完美了，實際上不是，雖然備忘錄解法把無用的重復求解都優化了，在速度上達到了比較優的程度。
但是對于第一次求解，未被記憶化的值來說，還是會進入遞歸調用邏輯。
比如 f(10000)，那么必然會遞歸調用 f(9999)、f(9998) ...... f(0)，而在遞歸的過程中，這些調用棧是不斷疊加的，當函數調用的深處，棧已經達到了成千上萬層。
此時它就會報出一個我們熟悉的錯誤：
- RangeError: Maximum call stack size exceeded
- at c:\codes\leetcode-javascript\動態規劃\斐波那契數列-509.js:20:19
- at c:\codes\leetcode-javascript\動態規劃\斐波那契數列-509.js:32:14
我們回過頭來思考一下，備忘錄的思路下我們的解法路徑是「自頂向下」的，如果我們把思路倒置一下，變成「自底向上」的求解呢?
也就是說，對于 fib(10000)，我們從 fib(1), fib(2), fib(3) ...... fib(10000)，
從最小的值開始求解，并且把每次求解的值保存在“記憶”(可以是一個數組，下標正好用來對應 n 的解答值)里，下面的值都由記憶中的值直接得出。
這樣等到算到 10000 的時候，我們想要求解的值自然也就得到了，直接從 記憶[10000] 里取到值返回即可。
那么這種解法其實只需要一個 for 循環，而不需要任何遞歸的邏輯。
其實這就是「動態規劃」的一種比較經典的解法啦，那么這種算法強力嗎?
對于 fib(10000) 這個上面兩種解法都無能為力的情況來說，它花了 0.114 秒就得出了結果。
對于 fib(100000) 它花了 0.827 秒。
對了，在 JavaScript 中這個數字由于超出最大值，會被展示成 Infinity，其實解決方法也很簡單，用 BigInt 的數據類型即可。
總結
本文用一個簡單的斐波那契數列的例子來體會了動態規劃算法的美感，以及它的強大能力。相信看完這篇文章的你，能夠知道算法并不是用來炫技的，而是真切的可以解決效率問題的。
