python - 在这个硬币找零问题中，我该如何做 "recursive"for 循环？

Question

我正在尝试解决硬币找零问题。您获得一定数额的钱(例如 55 美分)，并且必须回馈尽可能少的硬币。

我的解决方案非常简单(而且可能效率极低)。我尝试用蛮力来做到这一点。

首先，我尝试使用硬编码的固定硬币来实现，效果很好

money = 55

def findMinCoins(money):
    nq = int(money/25)
    nd = int(money/10)
    nc = int(money/1)
    smallest = nq + nd + nc
    for q in range(nq+1):
        for d in range(nd+1):
            for c in range(nc+1):
                if q*25 + d*10 + c == money:
                    if q + d + c < smallest:
                        smallest = q + d + c
                        print(q, d, c)
    return smallest

之后，我尝试使用硬币数组(例如 coin = [25, 10, 1])来完成此操作，这就是我的问题。

coins = [25, 10, 1]

def findMinCoins(money, coins):
    n_coins = [(int(money/coin) for coin in coins)]
    smallest = sum(n_coins)

我不知道应该如何对数组进行 for 循环。有人可以帮我找到解决方案吗？

Answer 1

可以对当前金钱中扣除的每个币进行递归调用，并从调用的返回值中获取最小值。如果扣除结果金额小于 0，则返回无穷大，这样就不会被认为是可行的:

def findMinCoins(money, coins):
    if money < 0:
        return float('inf')
    return money and min(findMinCoins(money - coin, coins) for coin in coins) + 1

这样:

findMinCoins(55, [25, 10, 1])

返回:

4

然而，上面的递归很慢，因为在考虑不同的路径时，它会用相同的金额进行大量的调用。您可以通过使用字典作为缓存来记住给定的金额和硬币组合的结果，从而显着提高性能:

def findMinCoins(money, coins, cache={}):
    key = money, tuple(coins)
    if key in cache:
        return cache[key]
    if money < 0:
        number = float('inf')
    else:
        number = money and min(findMinCoins(money - coin, coins) for coin in coins) + 1
    cache[key] = number
    return number