Почему это решение не работает для алгоритма замены монет?

Question

Напишите программу, в которой сумма N для внесения изменений и количество типов бесконечно доступных монет и список из 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