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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
import math

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        f = [0] + [math.inf] * aim
        for x in arr:
            for c in range(x, aim + 1):
                f[c] = min(f[c], f[c - x] + 1)
        return f[-1] if f[-1] < math.inf else -1