[演算法] 動態規劃 (Dynamic Programming)

使用 Kotlin 示範

Andy Lu

4 min readDec 31, 2020

什麼是動態規劃?

一個問題可以分解成多個小問題，而且每一個小問題又可以再分為更小的問題，直到無法分解。當把問題分解成眾多小問題時，同時將小問題的答案儲存起來，在其他部分若有使用到相同的問題，那麼就可以直接從以儲存的答案中讀取出來，減少重複的計算次數。

聽起來很抽象，簡單來說，動態規劃就是將問題分解成小問題，並將每一個小問題都儲存起來，所以當重複的小問題出現時，就可以省去已經計算過的小問題的計算時間。

範例：費式數列 (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 開始執行。由最下方的節點，計算到最上方的結果。