- class Solution:
- def coinChange(self, coins: List[int], amount: int) -> int:
- dp=[float('inf')]*(amount+1)
- dp[0]=0
- for coin in coins: #从最小的硬币开始，可能是最多的次数
- for j in range(coin,amount+1): #不能超过所求金额
- dp[j]=min(dp[j],dp[j-coin]+1)
- return dp[amount] if dp[amount]!=float('inf') else -1
- #没有任何一种硬币组合能组成总金额 的标志： dp[amount]!=float('inf')
amount+1√
amount×
float('inf')常用来表示最大值