322. Coin Change (Medium) and Dynamic Programming

322. Coin Change

Medium

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:
You may assume that you have an infinite number of each kind of coin.

答案使用O(nk)時間，其中n是金額，k是硬幣總類數量。

方法是，假設我們早已得知amount=9的最少硬幣數量是3個，那麼amount=10的硬幣數量要嘛就是amount=10-1=9的數量3加1，或者是amount=10-2=8的數量3加1，或者是amount=10-5的數量1加1，是3者的最少數值。

換一個角度：
amount=10數值與9，8，5有關
amount=9數值與8，7，4有關
amount=8數值與7，6，3有關
amount=5數值與4，3，0有關
amount=2數值與1，0，-3有關
amount=1數值與0，-1，-4有關
amount=0數值與-1，-2，-5有關
amount=-1數值與-2，-3，-6有關

由於求最少值因此使用其相反的最大值math.inf表示無法湊合金額。其中比較特比的是，預設amount負數的數值使用math.inf去表示好像很合理，但是從負數到整數的計算會一直得到math.inf，因此演算過程中需要設定一個起點不為math.inf的地方，通常這個地方坐落-1、0、1的位置。湊零錢這個問題如果考慮要湊出零元就是最佳的起點了，因此預設湊出0元的數量為0，其他預設math.inf就可以。

從$1開始計算到amount=$11，每個金額都考慮使用每一個硬幣之後所需的最少硬幣數目。

class Solution:

    def coinChange(self, coins: List[int], amount: int) -> int:

        dp = {0:0}

        for x in range(1, amount+1):

            for c in coins:

                dp[x] = min(dp.get(x, math.inf), 1+dp.get(x-c, math.inf))

        return dp[amount] if dp[amount]!=math.inf else -1

End