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