Warum funktioniert diese Lösung nicht für den Münzwechselalgorithmus?

Question

Schreiben Sie ein Programm, das, in Anbetracht der Menge N, um für und die Anzahl der Arten von m unendlich verfügbaren Münzen zu ändern, und eine Liste von M-Münzen, wie viele verschiedene Möglichkeiten Sie von den Münzen zu STDOUT wechseln können. Meine Intuition war, für jede Münze, diese Münze zu versuchen, und recurse auf n - c, wobei c der Wert der Münze ist, 1 zurückgebend, wenn ich zu Null komme und 0, wenn ich unter Null komme. Ich habe die vorher verwendete Münze eingestrichen und bin nur auf Münzen zurückgegangen, die kleiner oder gleich der vorherigen Münze waren, um Duplikate zu verhindern. Ich bin verwirrt, warum dieser Ansatz falsch ist und wie ich ihn korrigieren kann.

Hier ist mein Code:

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 

Sie für jede Hilfe danken.

Answer 1

Sie indexieren cache entsprechend der Menge, die Sie bis zu n hinzufügen möchten. Das Problem ist, dass die Anzahl der Kombinationen für die gleichen n je nach der Menge der Münzen, die Sie betrachten möchten, ändern kann. (ZB n=10 und coins=[10,5] hat zwei mögliche Kombinationen, aber n=10 und coins=[5] hat nur eine Kombination. Sie benötigen eine Cache die current_coin Variable zu betrachten.

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