Dynamic programming 是大學部演算法課程裡相當重要的一個主題，也是典型用空間換取時間的策略．但奇怪的是，這個策略一點也不 dynamic ，一點也不 programming．老實說，我不知道為何這個策略叫 dynamic prograaming，我倒覺得它比較適合叫 "查表法". 接著就來看看為何說它是查表法.
Fibonacci number 是許多演算法課本用來解釋 dynamic programming 最簡單的例子．Fibonacci number 是以數學多項式來表達的數字集合，以數學式來表達就可以寫成如下:
F(n) = F(n-1) + F(n-2)
也就是說求第 10 項 (n=10) 的答案時，你必須要先算出來第 9 項和第 8 項. 如果要求第 1 項呢 ? 難道要找出第 0 項和第 -1 項嗎 ? 在 Fibonacci number 上，我們會為這個 number 定義起始點，也就是說第 1 項和第 2 項的值是早被確定的，往後的項次皆由這兩項為基礎而算出來，所以不會有第 -1 項的情況. 假設, F(0) = 0, F(1) = 1 ，那麼數列的答案如下:
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8 以此類推
當你要算第 n 項時，就按以上的方法一直算到第 n 項就能得到答案. 接著，數學公式 F(n) = F(n-1) + F(n-2) 寫出來了，那麼寫程式碼就變得相當簡單.
透過一個 recursive function 就能快速完成 Fibonacci number 第 n 項的計算程式．這一個程式碼沒有使用額外的記憶體空間，所以 space complexity 是 O(1)，但仔細看一下 time complexity，卻發現超乎想像的大，因為有許多重覆的步驟:
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)
/ \
F(2) F(1)
上圖是整個 recursive 的關係. 意思就是，當程式在 F(5) 那一個層次要往下呼叫時，程式會呼叫自己兩次，並傳送 4 和 3 為輸入參數，當第一個 recursive call 再進去時，又會再呼叫自己，並傳入 3 和 2 為輸入參數，以此類推．所以你可以看的出來，有許多重覆的計算在這 recursive 的過程中一直發生．以上圖來說，F(3) 發生了 2 次，F(2) 發生了 3 次．當 n 是一個大的數字時，你就可以發現比 n 越小的數字，重覆計算的次數越多，並且是以指數趨勢來增加．上述的程式碼雖然很簡單，但是 time complexity 卻是很可怕的．上述的程式碼是由上而下計算下來的，假設我們繼續用由上而下的計算方式，改良此程式碼的方法就是將 "重覆" 的計算步驟讓它不要重覆計算．如上圖，如果 F(3) 只真正地被計算了一次，而 F(2) 只真正地被計算了一次，那麼就不會有重覆計算的事情了．為了達成這目標，最簡單的方法便是把計算後的結果儲存下來，等到要計算一樣的內容時，去 "查表" 即可．也就是說第一次 F(3) 計算的結果儲存下來，當程式遇到第二次的 F(3) 時，直接去查詢，若有答案，直接將答案拿來使用，這樣就不用計算了．同時，為了確保不會造成過多的 time complexity，我們也需要確認答案的儲存和查詢所花費的 time complexity 要非常小，如 O(1)．這種 "查表" 的精神也是 dynamic programming 所代表的策略．
若將上述的程式碼加入 "查表" 的功能，它將看起來如下:
或是直接改成由下往上計算
以上兩個程式碼雖然結構有點不太一樣，但都是用了一個 array 來記錄每一個項次計算的答案，因此 time complexity 省下來了，而且 space complexity 也增加了，但這樣的空間增加似乎是值得的．當然也可以再把上述的程式碼繼續改下去讓 space complexity 變的更小，不過這並不是這篇文章的重點．透過以上的簡單例子讓大家方便了解 dynamic programming 的 "查表" 意義是什麼．許多世界上有名的演算法都是基於 dynamic programming 的精神所發展出來的，例如你幾乎每天都在用的字串比對演算法就是基於 dynamic programming 所發明出來．
這篇文章用 Fibonacci number 的例子來說明 dynamic programming 的精神，這是相當簡單的例子，下篇文章我們用較難的例子來說明 dynamic programming 的用法.
