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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        if len(arr) == 0:
            return -1
        dp = [0] * (aim+1) # 0到aim
        for i in range(1,aim+1): # aim=0结果是0，从1开始，1是当前aim
            tmp = i+1            # 初始值，如果最后没变，返回-1
            for num in arr:
                if i-num>=0:     # 如果减去num<0肯定不行
                    if dp[i-num] != -1 and dp[i-num]+1 < tmp: # i-num是不行的，1肯定也不行
                        tmp = dp[i-num] + 1     # 如果有更小的tmp则更新
            if tmp != i+1:       # 发生过更新则添加需要多少张，如果没更新说明没办法达成
                dp[i] = tmp
            else:
                dp[i] = -1
        return dp[-1]