1 題目描述

給定不同面額的硬幣coin和一個總金額amount，寫一個函數來計算可以製造出總金額的最少硬幣數量。如果無法製造出總金額，則返回-1。

2 解法

其實dp的題目中有個共通點，都像是書包題目，為什麼是 dp 問題是因為可以拆分成小問題，而 amount 的小問題基本上就是 range(1, amount+1) 這些範圍如果都能夠找到最佳解ㄝ那自然amount也能找到最佳解。所以我們腦子有個思路，就是我們可以先從1開始。而最小值就是0，因為0元不需要硬幣。

小問題開始

# 初始化 dp 碰到 0 的 amount 就是 0
dp = {0: 0} 
# 因為 range 是不包含最後一個數字，所以要 +1 
for i in range(1, amount+1): 
    # 初始化 dp[i] 為無限大
    dp[i] = float('inf')

接下來，我們假設: amount=11 且 coins=[3, 5]，我們可以看到dp的變化如下：

dp[0] = 0
dp[1] = inf 沒有對應的 coin
dp[2] = inf 沒有對應的 coin
dp[3] = 1 因為有 coin 3 可以組成
dp[4] = inf 沒有對應的 coin
dp[5] = 1 因為有 coin 5 可以組成
dp[6] = 2 當 i>coin時基本上有2種可能取最小
- dp[6-3] + dp[3] = 1+1 = 2
- dp[6-5] + dp[5] = inf+1 = inf
dp[7] = 2 當 i>coin時基本上有2種可能取最小
- dp[7-3] + dp[3] = 1+1 = 2
- dp[7-5] + dp[5] = inf+1 = inf
dp[8] = 2 當 i>coin時基本上有2種可能取最小
- dp[8-3] + dp[3] = 1+1 = 2
- dp[8-5] + dp[5] = 1+1 = 2

有沒有發現上面有個規律

當i > coin時，我們可以看到dp[i]的值是dp[i-coin] + dp[coin]
當i < coin時，dp[i]的值是float('inf')，因為無法組成
當i == coin時，dp[i]的值是1，因為只有一個硬幣就可以組成，但其實他也可以寫成dp[i] = dp[i-coin]+dp[coin]因為會得到dp[0]+dp[coin]

然後所有的dp[coin]都是1，最後回傳值就是dp[amount]，如果dp[amount]是inf就回傳-1。

dp = {0: 0} 
for i in range(1, amount+1):
    dp[i] = float('inf')
    for coin in coins:
        if i == coin:
            dp[i] = 1
        elif i > coin:
            dp[i] = min(dp[i], dp[i-coin]+1) # dp[i-coin] + dp[coin] = dp[i-coin] + 1 

return dp[amount] if dp[amount] != float('inf') else -1

2.2 反過來

如果我們for loop外層先從coin開始，內層再for loop i的好處是不用比較i和coin的大小，因為i一定大於等於coin。
可以讓程式碼更簡潔

dp = [0] + [float('inf')] * amount
for coin in coins:
    for i in range(coin, amount+1):
        dp[i] = min(dp[i], dp[i-coin]+1)

return dp[amount] if dp[amount] != float('inf') else -1

時間複雜度： $O(n*m)$

n 是 amount
m 是 coins
空間複雜度： $O(n)$
n 是 amount

3 總結

所有碰到dp的題目，這種類似的背包問題都有個共通性…
那就是如果使用for loop的時候，要從包背最小空間開始找到最佳解，也就是題目的for i in range(i, amount+1)作為最外層開始。然後裡面的物品coin就是內層的for coin in coins，最後找到每個dp[i]的最佳解。並且找到dp[i]與上一個可行的最佳解。舉例來說：