达到给定金额所需的最少硬币数量。您拥有各种面额的无限硬币。了解优化

Question

问题：

您将获得一个表示不同面额硬币的整数数组硬币和一个表示总金额的整数金额。 返回弥补该金额所需的最少数量的硬币。如果该金额不能由任何硬币组合组成，则返回 -1。 您可以假设您拥有无限数量的每种硬币。

解决方案：

        @cache
        def dfs(rem):
            if rem == 0:
                return 0

            min_cost = float('inf')

            for coin in coins: 
                if rem / coin > min_cost: #???????????
                    break

                if rem - coin >= 0:
                    min_cost = min(min_cost, dfs(rem - coin) + 1)

            return min_cost

        # coins.sort(reverse=True)
        res = dfs(amount)
        return res if res != float('inf') else -1

如果我使用我用 #???????????? 标记的优化步骤，代码会明显更快。在上面的代码中。为什么这个优化步骤有意义？我知道该数组是反向排序的，但是，这并不像我们在该迭代中仅使用硬币或较低面额来弥补金额。我认为我们也在使用更大的面额。这在行中给出

if rem - coin >= 0:
    min_cost = min(min_cost, dfs(rem - coin) + 1)

为什么

dfs(rem-coin) + 1

总是大于

rem / coin

Answer 1

此条件基于以下观察：

• 如果从现在开始我们只使用当前的硬币，并且这将导致硬币的数量大于我们迄今为止找到的最好的硬币，我们可以得出结论，我们至少需要一枚价值更高的硬币，如果我们希望能够改进我们迄今为止发现的最好的。

• 但是，所有更大的硬币（比当前的硬币）已经在当前循环的先前迭代（包括递归搜索）中尝试过，因此我们迄今为止所拥有的最好的硬币已经反映了我们可以使用一个或多个硬币来做什么那些更大的硬币。此时我们不需要再使用它们，因为我们已经获得了此类尝试的最佳结果。

将这两个观察结果放在一起，我们知道如果这个

if

条件为真，我们就可以跳出循环。