湊零錢問題是這樣的：

給出K種硬幣，他們的數值分別是C1，C2，C3．．．CK，每種硬幣的個數都不限．

然後給出一個總數Amount，使用最少的硬幣湊出這個Amount．如果湊不出來，則回傳-1

輸入的形式大概如下:

fun coinChange(coins:IntArray,amount:Int):Int
//coins是硬幣的面值，amount是目標金額

例如K=3 ，這三種硬幣的面額分別1，2，5，要湊出amount = 11．

則最少需要三個硬幣，分別是 5+5+1．

最佳子結構

一個具有最佳子結構的問題，所有子問題之間的解答必須互相獨立不干擾．不能因為其中一個子問題的答案影響到另外一個子問題的答案，比如硬幣的個數有數目限制，因此在解決要湊出B的子問題時，可能在A問題就已經用完所有的硬幣了，這樣AB問題之間就具有互相影響的性質，不能稱為最佳子結構．

但是這個問題硬幣的數目是無限的，也因此如果要湊出11塊錢，可以利用湊出10塊錢的子問題，再增加一枚1元硬幣來解決(如果有1元的面額)，所以在無限硬幣的情況下，這個問題就具有最佳子結構．

首先我們先用暴力解的方法做做看這題動態規劃

暴力遞回

帶上前面說到的動態規劃範本

1.確定初始狀態:很簡單，題目的amount = 0的時候，返回0枚硬幣．所以初始狀況就是 0

2.確定狀態:也就是原問題與子問題之間互相變化的數值，那在解題過程中．逐漸改變貼近的就是題目的目標數額amount

3.確定選擇:導致狀態變化的動作，在這個題目就是選擇了某一枚硬幣，導致總數值逐漸往目標的amount前進．所以所有的硬幣面額就是選擇的集合．

4.明確狀態變化的dp函數:輸入值通常就是狀態轉移的狀態，返回值則是要求計算的量．

所以這題就是:輸入一個目標金額n，返回湊出目標金額的最少硬幣數目

那麼暴力破解的程式碼如下：

fun coinChange(coins: IntArray, amount: Int): Int {

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

    return dp(amount)
}

我們來執行看看

fun main() {
    val coins = intArrayOf(1,2,5)
    println(coinChange(coins,11))
}

答案為3，由於這測資很簡單，就略過驗證流程了
明天我們會來優化這個暴力的解法