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

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        if aim == 0:
            return 0
        arr.sort()
        dp = [float('inf')]*(aim+1)
        for j in arr:
            if j <= aim:
                dp[j] = 1
        for i in range(1,aim+1):
            for j in arr:
                if i-j>-1 and dp[i-j] != -1:
                    dp[i] = min(dp[i],dp[i-j]+1)
        if dp[aim] == float('inf'):
            return -1
        return dp[aim]