为什么这个解决方案不适用于硬币找零算法？

Question

编写一个程序，给定要找零的数量 N 和 m 种无限可用硬币的类型数量，以及 m 种硬币的列表，打印出您可以从这些硬币找零到标准输出。

我的直觉是，对于每个硬币，尝试那个硬币，并在 n - c 上递归，其中 c 是硬币的价值，如果我达到零则返回 1，如果我低于零则返回 0。我传入了之前使用过的硬币，并且只对小于或等于之前硬币的硬币进行递归，以防止重复。我很困惑为什么这种方法不正确，以及如何纠正它。

这是我的代码：

def calc_change(n, coins):
    cache = {}
    c = max(coins)
    nums = calc_ways(n, coins, cache, c)
    return nums

def calc_ways(n, coins, cache, current_coin):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if n not in cache:
        cache[n] = sum(calc_ways(n - c, coins, cache, c) for c in coins if c <= current_coin)
    return cache[n]

answer = calc_change(n, coins) 
print answer

感谢您的帮助。

Answer 1

您正在根据您要加起来 n 的金额编制索引 cache。问题是相同 n 的组合数量可能会根据您要考虑的硬币组而变化。（例如 n=10 和 coins=[10,5] 有两种可能的组合，但是 n=10 和 coins=[5] 只有一种组合。您需要缓存考虑 current_coin 变量。

def calc_change(n, coins):
    cache = {}
    c = max(coins)
    nums = calc_ways(n, coins, cache, c)
    return nums

def calc_ways(n, coins, cache, current_coin):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if (n,current_coin) not in cache:
        cache[(n,current_coin)] = sum(calc_ways(n - c, coins, cache, c) for c in coins if c <= current_coin)
    return cache[(n,current_coin)]

answer = calc_change(n, coins) 
print answer

为什么这个解决方案不适用于硬币找零算法？

Why this solution isn't working for the coin change algorithm?

python

algorithm

coin-change