LC 322零钱兑换Coin Change　中等

给定不同面额硬币 coins 和总金额 amount，求凑出总金额所需的最少硬币个数，凑不出返回 -1。

思路 完全背包：dp[i] = 凑出金额 i 的最少枚数，枚举最后一枚硬币转移。时间 O(n·amount)。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [inf] * amount
        for x in coins:
            for i in range(x, amount + 1):
                dp[i] = min(dp[i], dp[i - x] + 1)
        return -1 if dp[amount] == inf else dp[amount]