コインチェンジアルゴリズムでこのソリューションが機能しないのはなぜですか？

Question

無制限に利用可能なコインの種類と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

nに追加する金額に応じてcacheのインデックスを作成しています。問題は、同じnの組み合わせの量が、考慮したいコインのセットによって変わる可能性があることです。 （例えばn=10とcoins=[10,5]は、2つの可能な組み合わせを持っていますが、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