假设给你不同面额的硬币和一个金额amount。编写一个函数来计算构成该金额amount
所需的最少数量的硬币。如果这笔钱不能由任何硬币组合成,则返回-1。
动态规划:
dp[i]=min(dp[i],dp[i-coin]+1)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp=[amount+1]*(amount+1)
dp[0]=0
for i in range(1,amount+1):
for c in coins:
if i>=c:
dp[i]=min(dp[i],dp[i-c]+1)
if dp[amount]==amount+1:
return -1
return dp[amount]