Ten problem jest taki sam, jak w pytaniututaj.

Biorąc pod uwagę listę monet, ich wartości (c1, c2, c3, ... cj, ...) oraz całkowitą sumę i. Znajdź minimalną liczbę monet, których suma to i (możemy użyć tyle monet, ile chcemy) lub zgłoś, że nie można wybrać monet w taki sposób, aby sumowały się do S.

Właśnie wczoraj wprowadzono mnie do programowania dynamicznego i próbowałem zrobić dla niego kod.

# 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

Tutaj C [i] jest optymalnym rozwiązaniem dla ilości pieniędzy „i”. A dostępne monety to {c1, c2, ..., cj, ...} dla programu, zwiększyłem limit rekursji, aby uniknąć błędu przekroczenia maksymalnej głębokości rekurencji. Ale ten program daje właściwą odpowiedź tylko niektórym, a gdy rozwiązanie nie jest możliwe, nie oznacza to.

Co jest nie tak z moim kodem i jak go naprawić?