Dieses Problem ist dasselbe wie in gefragtHier.

Ausgehend von einer Liste von Münzen, ihren Werten (c1, c2, c3, ... cj, ...) und der Gesamtsumme i. Finden Sie die Mindestanzahl an Münzen, deren Summe i ist (wir können so viele Münzen eines Typs verwenden, wie wir möchten), oder melden Sie, dass es nicht möglich ist, Münzen so auszuwählen, dass sie sich zu S summieren.

Ich bin erst gestern in die dynamische Programmierung eingeführt worden und habe versucht, einen Code dafür zu erstellen.

# Optimal substructure: C[i] = 1 + min_j(C[i-cj])
cdict = {}
def C(i, coins):

    if i <= 0:
        return 0

    if i in cdict:
        return cdict[i]
    else:
        answer = 1 + min([C(i - cj, coins) for cj in coins])
        cdict[i] = answer
        return answer

Hier ist C [i] die optimale Lösung für den Geldbetrag 'i'. Und verfügbare Münzen sind {c1, c2, ..., cj, ...} für das Programm. Ich habe das Rekursionslimit erhöht, um zu vermeiden, dass die maximale Rekursionstiefe den Fehler überschreitet. Aber dieses Programm gibt nur einigen die richtige Antwort und wenn eine Lösung nicht möglich ist, zeigt es dies nicht an.

Was ist falsch an meinem Code und wie kann ich ihn korrigieren?