#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @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=[aim+1]*(aim+1)
        dp[0]=0  # 金额为0 
        for coin in arr:
            for  j in range(coin,aim+1):
                dp[j]=min(dp[j],dp[j-coin]+1)
        if dp[aim]>aim:
            return -1 
        else:
            return dp[aim]