0

我现在正在研究 Leetcode 322. Coin Change，问题如下：

给你一个整数数组coins，表示不同面额的硬币，一个整数表示总金额。

返回您需要的最少数量的硬币来弥补该金额。如果该金额不能由任何硬币组合弥补，则返回-1。

您可以假设您拥有无限数量的每种硬币。

示例 1：

输入：coins = [1,2,5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

我试图通过带有记忆的自上而下的 DP 来解决它。我在辅助函数中设置了一个参数来记住计数。

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。

我整个下午都试图弄清楚，但不知道我哪里做错了。我希望你能给我一些建议，我哪里出错了。

在此先感谢您的帮助。

4

1 回答 1

0

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

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

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

解释：

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

所以首先要做的是将列表从最大到最小的数字排序，如.sort()函数所示。

然后对于该列表中的每个数字（for 循环从列表中的第一项开始，因此最大的数字）将它们放入 while True 循环中，以便它们不断添加到总数中，直到满足条件：

有3个条件：

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

  2. 如果当前金额 + 列表中的当前项目大于刚刚突破的最终金额（这确保不再添加此类数字）

  3. 最常用的是检查当前金额是否小于最终金额，但重要的是它们是elif陈述，因为在这种情况下，如果一个陈述被证明是真的，它不会检查在这种情况下不需要休息，因为否则即使您无法在当前金额中添加更多内容以不超过最终金额，它也会被证明是正确的。

  4. 这个 if 语句在循环之外，while True并在数字“突破”while True循环时检查最终数量是否匹配，这是为了防止连续检查，即使结果已经实现。

然后对结果进行评估，如果当前金额与最终打印 -1 不匹配，则打印计数

于 2021-04-13T01:05:19.877 回答