➣ Reading Time: 4 minutes

前言

這是我自己理解後所做的演算法筆記。

動態規劃 (Dynamic programming,DP)

先備知識

討論動態規劃前,我們要先有 divide and conquer (將大問題化為多個小問題) 的觀念,
我們先將大問題化為多個小問題後,開始分析這些小問題裡面,
如何最佳化我們演算的效率。

觀念

動態規劃 (Dynamic programming,DP) 中,我們更著重在討論這些小問題 (或說子問題),
怎麼樣去解決才能夠有最佳效率,我們會發現,在很多大問題化為的子問題中,
我們會碰到大量的「解決相同(重複)子問題」情況,造成演算效率變差。

例子

我們舉最經典的「費波納奇數列」為例:

  • f(0) = 0
  • f(1) = 1
  • f(x) = f(x-1) + f(x-2) (n >= 2)

未使用動態規劃 解 f(5)

每一個箭頭,都表示我們要做一次加法,

我們的總計算量 = 14 次

使用動態規劃 解 f(5)

我們先建立一個表格,當算出一次結果時,就保存在表中。

xf(x)
00
11
21
32
43
55
  • 於是透過查表產剩下面的結果:

每一個箭頭,都表示我們要做一次加法,
藍色箭頭表示我們因為已經算過一次 (並儲存答案在表中),
所以我們直接查表找答案。

我們的總計算量 = 8 次

結論

雖然上面的例子看起來不會差太多,
那是因為我們舉的例子數字還小,

實際上的「時間複雜度」:

  • 未使用 DP: O(2^n) -> 約 2 的 n 次方
  • 使用 DP: O(n)

這樣有沒有使用 DP 的差別就夠明顯了吧!

Reference

https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://zh.codeprj.com/blog/66e3901.html
https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
Dynamic Programming Explanation with Fibonacci 用費波那契數列來入手動態規劃