题解 | #兑换零钱(一)#带备忘录的递归解法

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#备忘录+递归算法
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        mem=[-666]*(aim+1)
        if arr==[]:
            return -1
        def dp(arr,aim):
            if aim<0:
                return -1
            if aim==0:
                return 0
            if mem[aim]!=-666:
                return mem[aim]
            res=100000
            for coin in arr:
                if dp(arr,aim-coin)==-1:
                    continue
                res=min(res,dp(arr,aim-coin)+1)
            mem[aim] = -1 if res == 100000 else res
            
            return mem[aim]
        return dp(arr,aim)
        
            
            

            
        # write code here