優化計算費波那契數的方法 — 動態規劃

大家好，首先先祝福大家身心靈健康。

不知道大家有沒有看過上一篇介紹用遞迴的方法計算費波那契數的文章呢？還沒看的朋友可以點這裡去看看喔！

幫大家回顧一下，使用遞迴的方法計算費波那契數，時間複雜度是 O(φ^n)。以我的運行環境，計算 fibonacci(100) 可能需要五至七萬年左右的時間。

怎麼優化呢？我們可以使用動態規劃（dynamic programming）的方法，避免重複計算相同的子問題，從而提高計算的效率。

動態規劃的核心思想是把中間計算的結果記錄起來，未來需要的時候可以直接使用，而不用重新計算。

下面，我們看看如何用自底向上的動態規劃方法，來計算費波那契數。這種計算方法從下到上計算所有的費波那契數，並暫存在一個陣列中：

function fibonacci(n) {
  if (n <= 1) return n;

  const dp = new Array(n + 1);
  dp[0] = BigInt(0);
  dp[1] = BigInt(1);

  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(fibonacci(100)); // 354224848179261915075n

因為費波那契數列中每個數值只需要被計算一次，因此使用這樣子的計算方法，時間複雜度就從 O(φ^n) 降低為 O(n)。以我的環境執行以上的程式碼，不到 1 毫秒就可以計算出 fibonacci(100) 了。