Este problema es el mismo que se pregunta enaquí.

Dada una lista de monedas, sus valores (c1, c2, c3, ... cj, ...), y la suma total i. Encuentre el número mínimo de monedas cuya suma es i (podemos usar tantas monedas de un tipo como queramos), o informe que no es posible seleccionar monedas de tal manera que sumen S.

Ayer me introduje en la programación dinámica y traté de hacer un código para ella.

# 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

Aquí, C [i] es la solución óptima para la cantidad de dinero 'i'. Y las monedas disponibles son {c1, c2, ..., cj, ...} para el programa, he aumentado el límite de recursión para evitar que la profundidad máxima de recursión haya superado el error. Pero, este programa da la respuesta correcta solo a alguien y cuando una solución no es posible, no lo indica.

¿Qué está mal con mi código y cómo corregirlo?