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

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here

        if aim < 1:
            return 0
        dp = [(aim+1) for i in range(aim+1)]
        dp[0] = 0


        for i in range(1, aim+1):
            for j in range(len(arr)):
                if arr[j] <= i: # 要开始凑钱了
                    dp[i] = min(dp[i], dp[i-arr[j]]+1)

        if dp[aim] > aim:
            return -1
        else:
            return dp[-1]