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

#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
# fx = f[x-arr_i] +1
import sys

class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        res = [sys.maxsize for i in range(aim+1)]
        res[0] = 0
        for i in range(1,aim+1):
            for j in arr:
                if i>=j and res[i-j]!=sys.maxsize:
                    res[i] = min(res[i],res[i-j]+1)
#         print(res)
        return res[-1] if res[-1]!=sys.maxsize else -1