JavaScript版本中如何從最簡單的斐波那契數列來學習動態規劃

這篇文章將為大家詳細講解有關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 的數據類型即可。

總結

希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。