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

# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # 首次提交的答案 (19/24，超时)
        # 提示1，dp：由题目给出的复杂度提示可看出，本题可转化为状态压缩的非0-1背包问题，其中item - n，weight - aim
        # 算法复杂度：最差情况，不同类型货币价格均为1，O(aim^2*n)
        if aim == 0:
            return 0

        dp = [0 for _ in range(aim+1)]
        n = len(arr)
        for i in range(n):
            for j in range(aim, 0, -1):  # 逆序遍历
                for k in range(j // arr[i] + 1):  # j - arr[i] * k >= 0, 向下取整
                    if dp[j - arr[i] * k] == 0 and j - arr[i] * k != 0:
                        continue

                    if dp[j] != 0:
                            dp[j] = min(dp[j], dp[j - arr[i] * k] + k)
                    else:
                        dp[j] = dp[j - arr[i] * k] + k
        if dp[-1] == 0:
            return -1
        else:
            return dp[-1]

        # 标准答案，先迭代目标面值aim而非迭代货币种类n
        # 1.因为目标面值aim迭代步长小于货币面值，每种货币的张数k的迭代可分散于aim的迭代中，复杂度：O(aim^2*n)
        # 2.由于货币种类n非逆序迭代，因而面值aim的每轮迭代，不同种类货币可重复挑选（货币种类n迭代时，dp数组状态会覆盖）
        # 算法复杂度：O(aim*n)
        #小于1的都返回0
        if aim < 1:
            return 0
        #dp[i]表示凑齐i元最少需要多少货币数
        dp = [(aim + 1) for i in range(aim + 1)]
        dp[0] = 0
        #遍历1-aim元
        for i in range(1, aim + 1):
            #每种面值的货币都要枚举
            for j in range(len(arr)):
                #如果面值不超过要凑的钱才能用
                if arr[j] <= i:
                    #维护最小值
                    dp[i] = min(dp[i], dp[i - arr[j]] + 1)
        #如果最终答案大于aim代表无解
        if dp[aim] > aim:
            return -1
        else:
            return dp[aim]