为什么此解决方案不适用于硬币更改算法？

Question

编写一个程序，给定要更改的数量N和m无限可用硬币的类型数量，以及m硬币的列表，打印出从硬币到STDOUT可以更改多少种不同的方式。

我的直觉是，对于每个硬币，尝试该硬币，并在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

您正在根据要加起来的量cache编制索引，最多n。问题是同一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