硬币兑换的自上而下方法中的问题（类似于0-1背包问题）

Question

我现在正在研究leetcode322。换硬币，问题如下：

您将获得一个整数数组，表示不同面额的硬币，以及一个整数金额，表示总金额。

返回您需要的最少数量的硬币，以弥补该金额。如果这些硬币的任何组合都无法弥补这一数额，则返回-1。

你可以假设每种硬币的数量是无限的。

例1：

输入：硬币=[1,2,5]，数量=11输出：3说明：11=5 1

例2：

输入：硬币=[2]，金额=3输出：-1

例3：

输入：硬币=[1]，金额=0输出：0

例4：

输入：硬币=[1]，金额=1输出：1

例5：

输入：硬币=[1]，金额=2输出：2

我试图通过自上而下的DP和记忆来解决这个问题。我在helper函数中设置了一个参数来记住计数。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        c = set(coins)
        dp = [0] * (amount + 1)

        def helper(a, count):
            if a == 0:
                return count
            # if a in c:
            #    return 1 + count
            if dp[a] != 0:
                return dp[a]
            res = math.inf
            for coin in c:
                if a - coin >= 0 and helper(a-coin, count+1) != -1:  
                    res = min(res, helper(a-coin, count+1))
            dp[a] = res if res < math.inf else -1
            return dp[a]

        return helper(amount, 0)

但该案不会通过，因为：

[1,2,5] 100

结果应该是20，但我得了92。

我整个下午都在想办法，但不确定哪里做错了。我希望你能给我一些建议，我哪里出了问题。

提前感谢你的帮助。

Answer 1

!!! 这是一个完整的解决方案！！！

好的，这是我对这个问题的解决方案（想法解释如下）：

def solve(lst, amount):
    lst.sort(key=lambda x: x, reverse=True)
    current_amount = 0
    count = 0
    for item in lst:
        while True:
            if current_amount + item == amount:
                count += 1
                current_amount += item
                break
            elif current_amount + item > amount:
                break
            elif current_amount < amount:
                count += 1
                current_amount += item
        if current_amount == amount:
            break

    if current_amount != amount:
        print(-1)
    else:
        print(count)


solve([1, 2, 5], 100)

产出：20

说明：

！！！主要思想
首先，你必须从列表中最大的数字开始，因为它需要最少的添加量来最接近或完全成为最终数量。！！！

因此，首先要做的是将列表从最大的数字html" target="_blank">排序到最小的数字，如所示。sort（）函数。

然后，对于该列表中的每个数字（对于循环，从列表中的第一个项目开始，所以是最大的数字），将它们放在一个而True循环中，以便它们继续添加到总数中，直到满足条件：

有3个条件：

>

当前金额（来自所有添加项）加上列表中的当前项等于最终金额，在这种情况下，将计数增加1，将当前项添加到总计，然后跳出循环

如果列表中当前项目的当前金额大于最终金额，则只需中断（这确保不会添加更多此类数字）

最常用的是检查当前量是否小于最终量的语句，但是它们是elif语句是很重要的，因为在这种情况下，如果一个语句被证明是真的，它就不是检查在这种情况下不需要的其余部分，因为否则即使您不能在当前金额中添加更多以不超过最终金额，它也会变成真的。

此if语句不在while True循环中，当while True循环中出现数字“中断”时，检查最终金额是否匹配，这是为了防止连续检查，即使结果已经达到。

然后计算结果，如果当前金额与最终打印不匹配-1，则打印计数