前言
這是我自己理解後所做的演算法筆記。
動態規劃 (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)
我們先建立一個表格，當算出一次結果時，就保存在表中。
| x | f(x) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
- 於是透過查表產剩下面的結果：
每一個箭頭，都表示我們要做一次加法，
藍色箭頭表示我們因為已經算過一次 (並儲存答案在表中)，
所以我們直接查表找答案。
我們的總計算量 = 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 用費波那契數列來入手動態規劃
[…] 【演算法筆記】動態規劃 (Dynamic programming，DP) […]