Эта проблема такая же, как вВот.

Given a list of coins, their values (c1, c2, c3, ... cj, ...), and the total sum i. Find the minimum number of coins the sum of which is i (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.

Вчера я только познакомился с динамическим программированием и попытался написать для него код.

# 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

Здесь C [i] является оптимальным решением для суммы денег 'i'. Доступные монеты: {c1, c2, ..., cj, ...} для программы я увеличил предел рекурсии, чтобы избежать ошибки превышения максимальной глубины рекурсии. Но эта программа дает правильный ответ только кому-то, и когда решение невозможно, это не указывает на это.

What is wrong with my code and how to correct it?