兑换零钱(一)

兑换零钱(一)_牛客题霸_牛客网

问题简述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.

数据范围：数组大小满足 100000 ≤ n ≤ 10000 ， 数组中每个数字都满足 0 < val ≤ 10000，0≤aim≤5000

要求：时间复杂度 O(n×aim) ，空间复杂度 O(aim)。

思路：动态规划

• 定义 dp(a) 表示凑出 a 元钱需要最小的零钱数量；

• 则 dp(a) = min(dp(a), dp(a - arr[j]) + 1) for j in range(len(arr))；

• TODO: 整理完全背包相关内容；

Python

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        import sys
        sys.setrecursionlimit(100000)
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(a):  # 凑出 a 元钱需要最小的零钱数量
            if a == 0:
                return 0
            
            ret = float('inf')
            for i in range(len(arr)):  # 对每种面值
                if a >= arr[i]:
                    # 如果 a 大于当前零钱面值；
                    # 则先兑换一张该面值的零钱，然后计算剩余钱数的最小零钱数量；
                    # 记录所有可能中的最小值
                    ret = min(ret, dp(a - arr[i]) + 1)
            
            return ret
        
        ret = dp(aim)
        return -1 if ret == float('inf') else ret