[演算法] 動態規劃 (Dynamic Programming)
什麼是動態規劃?
一個問題可以分解成多個小問題，而且每一個小問題又可以再分為更小的問題，直到無法分解。當把問題分解成眾多小問題時，同時將小問題的答案儲存起來，在其他部分若有使用到相同的問題，那麼就可以直接從以儲存的答案中讀取出來，減少重複的計算次數。
聽起來很抽象，簡單來說，動態規劃就是將問題分解成小問題，並將每一個小問題都儲存起來，所以當重複的小問題出現時，就可以省去已經計算過的小問題的計算時間。
範例：費式數列 (Fibonacci numbers)
fib(0) = ０，
fib(1) = 1，
fib(n) = fib(n-1) + fib(n-2)。
簡單列出前面幾項，如下圖：
如果要用程式來實作，該如何進行呢？
遞迴(Recursion)
fun fib(i:Int): Int{
if(i == 0) return 0
if(i == 1) return 1
return fib(i - 1) + fib(i - 2)
}每一次呼叫 fib 的時候，都會將遞迴的樹展開，效率相當不好，花費的時間複雜度會是 O(2^n)。
將 index 為 5 的 費氏數列化成樹狀圖，如下：
注意到什麼了嗎？
fib(3) 被呼叫 兩次，fib(2)被呼叫 3 次。
動態規劃 (Dynamic Programming)
複習一下動態規劃的定義(就在最前面)：動態規劃就是將問題分解成小問題，並將每一個小問題都儲存起來，所以當重複的小問題出現時，就可以省去已經計算過的小問題的計算時間。
我們若將費氏數列採用動態規劃的方式運算，計算 fib(5)的數列則可省去 3 次遞迴呼叫，fib(3) 1 次，fib(2) 2 次。
var mem = emptyArray<Int?>()fun fibDP(i: Int): Int {
if (mem.isEmpty()) {
mem = arrayOfNulls<Int?>(i + 1)
}
if (mem[i] != null) {
return mem[i]!!
} else {
if (i == 0) {
mem[i] = 0
return 0
}
if (i == 1) {
mem[i] = 1
return 1
}
mem[i] = fibDP(i - 1) + fibDP(i - 2)
return mem[i]!!
}
}
這種方式是從資料的樹的最上方，計算到最下方，所以也稱為 Top-Down Dynamic Programming 由上至下的動態規劃。
雖然減少了很多次小問題的計算，但是卻還是需要多次的遞迴才有辦法計算出資料，某些程式語言在經過多次的遞迴之後，效率會變得不好。此時，我們可以考慮另一種動態規劃：
由下至上的動態規劃 (Bottom-Up Dynamic Programming)
在計算子問題的部分，我們不採用遞迴的方式，而是直接使用一個 for 迴圈來處理。
如下：
fun fibBottomUpDP(i: Int): Int {
if (i == 0) return 0
if (i == 1) return 1 val mem = arrayOfNulls<Int>(i + 1)
mem[0] = 0
mem[1] = 1 for (index in 2..i) {
mem[index] = mem[index - 1]!! + mem[index - 2]!!
}
return mem[i]!!
}
跟前面介紹的動態規劃不同的是，這種演算法不需要使用遞迴，所以速度又會比由上至下的動態規劃來得更快。
至於為什麼是由下至上。因為 for 迴圈是從 index 為 2 開始執行。由最下方的節點，計算到最上方的結果。
結論
動態規劃 (DP) 將重複的項目儲存起來，避免消耗不必要的時間計算。
利用記憶空間來換取時間，所以如果計算的數值越大，所需的記憶空間仍然會很大，所以在使用的時候，需要特別注意。
如果這篇文章有幫助到你，請拍手鼓勵我，
謝謝
