题解 | #兑换零钱(一)#
兑换零钱(一)
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
# 本题可以看作是完全背包问题的变形，以下代码是在研究背包问题时在网上拷贝的
class Solution:
def minMoney(self , arr: List[int], aim: int) -> int:# write code here
w = arr
c = aim
dp=[float('inf')]*(c+1)
dp[0]=0
for i in range(len(w)):
#print(1)
for j in range(w[i],c+1):
dp[j]=min(dp[j],dp[j-w[i]]+1)
return dp[c] if dp[c]!=float('inf') else -1
