Leetcode 322. Coin Change [Python]

Leetcode 322. Coin Change [Python]

经典贪心，但是用dp的方式来表示。首先建立amount的数组用来表示需要多少coins来组成这个amount（最小的coins数）。然后遍历coin里的amount unit。从coin的价值到amount进行遍历，只要当前价格 减去当前coin价值（面值），在dp数组里有相应的个数的银币组成，就可以得到，我们的i - coin需要的硬币个数加上一个coin面值的银币就能得到i这个amount的币面价值总和。当然了，dp[i]可能在遍历不同coin面值的时候被更新，所以需要保持最小价值。

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