题解 | 兑换零钱(一)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @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
        if len(arr) == 0:

            return -1
        dp = [aim+1] * (aim+1)
        dp[0] =  0

        for i in range(len(arr)):
            for j in range(arr[i], aim+1):
                dp[j] = min(dp[j-arr[i]]+1, dp[j])
        if dp[aim] == aim+1:
            return -1
        return dp[aim]