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