题解 | #兑换零钱(一)#dp数组解法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#dp数组解法
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
#dp数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。
        dp=[aim+1]*(aim+1)
        dp[0]=0
        for i in range(len(dp)):
            for coin in arr:
                if i<coin:
                    continue
                dp[i]=min(dp[i],dp[i-coin]+1)
        if dp[aim]==aim+1:
            return -1
        return dp[aim]


            
            

            
        # write code here