來看看昨天的遞迴圖

可以注意到兩個特點

1.在湊4元的時候，使用5元硬幣的狀態可以忽略

2.跟費波那契有同樣的狀況，有許多狀況可能被重複計算…

Memo版本

所以就照我們第４天學到的使用Memo來減少重複的計算量．

範例程式碼跟暴力計算差不多

只增加了一個memoArray的宣告．以及在開始計算前先看看memo裡面有沒有之前算過的答案．

fun coinChangeWithMemo(coins: IntArray, amount: Int): Int {
    val memoArray = IntArray(amount + 1)
    fun dp(n: Int): Int {
        return if (n > 0 && memoArray[n] > 0) {//memo裡面有答案，不用計算
            memoArray[n]
        } else if (n == 0) {
            0
        }//初始狀態為0
        else if (n < 0) {
            -1
        } else {
            var ans = Int.MAX_VALUE//因為求最小值，所以用Max作為初始...如果測資過大就要調整
            for (coin in coins) {
                val subProblem = dp(n - coin)//求子問題的解答
                if (subProblem == -1) continue //湊不出來，跳過這個硬幣
                ans = minOf(ans, 1 + subProblem)//尋找出子問題中答案比較小的那個
            }
            if (ans != Int.MAX_VALUE) {//有找到解答
                memoArray[n] = ans //把答案存進memo中
                ans
            } else {//沒有解答
                -1
            }
        }
    }
    return dp(amount)
}

執行起來如下

藉由短短幾行，我們就將時間複雜度降低到O(kn)的程度．

DP Table

有memo版本，那我們DP Table的版本也來一個，記得DP Table是怎樣解決問題的嗎，從基礎狀態一步一步推到最終狀態．．

fun coinChangeWithDPTable(coins: IntArray, amount: Int): Int {
    val dpArray = IntArray(amount + 1) { amount + 1 }//使用Array作為DP Table
    dpArray[0] = 0

    for (i in dpArray.indices) {//這層迴圈會把整個dpArray填滿
        for (coin in coins) {//這層迴圈把每個硬幣的最小值求出來
            if (i - coin < 0) continue
            else {
                dpArray[i] = minOf(dpArray[i], 1 + dpArray[i - coin])
            }
        }
    }

    return if (dpArray[amount] == amount + 1) { //目標值沒有湊出來
        -1
    } else {
        dpArray[amount] //有目標值直接回傳
    }
}

注意這邊這行

val dpArray = IntArray(amount + 1) { amount + 1 }

為什麼初始值使用amount+1呢，因為所有可能性中，最糟糕的情況就是amount(全部用1元硬幣湊出來就會如此０)，因此我們初始值使用amount+1，來確保有任何解答都能夠填入．

來執行看看

有沒有注意到Memo版本跟DPTable的時間有一咪咪的落差，在不同的動態規劃問題內就連簡化的方法也有不同的代價，當然不管哪個都比暴力好上不少

總結

這幾天我們用了兩個例子來說明動態規劃．

第一個費波那契數列問題，說明了如何使用Memo或是DP Table來最佳化遞迴的過程，只是一個是從目標狀態一步一步往初始狀態推進，而另一個從初始狀態一步一步往目標狀態推進，其實兩者本質上是相同的．

第二個湊零錢問題，我們實際演練了一次使用範本確定狀態轉移方程的方法，然後寫出了暴力解法，最後再使用技巧優化．

列出狀態轉移方程，便是解決如何列舉出全部狀態的問題．之所以困難，一是很多列舉需要使用遞迴去列出，另外一個是有的問題的解答空間很廣泛，不容易全部列出來．

我們再來複習一次，動態規劃問題的範式

1.確定初始狀態

2.確定狀態

3.確定選擇

4.明確狀態變化的dp函數

明天開始我們會開始進入回溯演算法內容