题解 | #兑换零钱(一)#

from pickle import PUT
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        dp= [99999 for j in range(aim+1)]
        dp[0]=0
        for j in range(1,aim+1):
            for i in range(len(arr)):
                #print(j,arr[i])
                if j>=arr[i]:
                    thisnum = dp[j-arr[i]]+1
                    #print(thisnum)
                    if thisnum < dp[j]:
                        dp[j] = thisnum
            
            #print(j,dp[j])
            
        if dp[-1]!=99999:
            return dp[-1]
        else:
            return -1