Смена монеты в питоне (рекурсивное решение)

Question

Я довольно новичок в python, и я практиковал пару проблем, которые я нашел в Интернете (это eulerproject q31). Я разобрался с 2 способами, чтобы решить это Проблема: выясните все способы, которыми вы можете внести изменения на определенную сумму денег, используя определенный набор монет, например доллар {1,5,10,25}

Это код, который у меня есть для моего рекурсивного решения

def count(s, m, n):
    if (n < 0):
        return 0;
    if (m <=0 and n >= 1):
        return 0
    if (n == 0):
        return 1
    return count( s, m - 1, n) + count(s, m, n-s[m-1] ); 

S - набор монет {1,5,10,25} m - длина набора монет (в данном случае 4), а n - сумма ввода

Это работает отлично, за исключением того, что когда я пытаюсь дать ему большее значение, например 7000, я посмотрел в Интернете, и кажется, что мое решение будет включать в себя подзадачи, которые были включены в предыдущую рекурсивную итерацию несколько раз (чтобы достичь максимума) предел рекурсии). Я пытаюсь понять, как это сделать, используя памятку, которую я смогу использовать на Java, но не знаю, как подойти к ней на python. Может ли кто-нибудь дать какие-либо указания относительно того, как мне следует запомнить этот алгоритм, чтобы он пропускал проверку подзадач, которые уже были проверены? Спасибо!

Answer 1

Сохраните рассчитанную вами сумму.

    def make_change2(coins, n):
        if n == 0:
            return 1
        if n < 0:
            return 0
        num_ways = 0
        dic_ways = {}
        for i in range(len(coins)):
            coin = coins[i]
            if n-coin not in dic_ways:
                num_ways += make_change(coins[i:], n - coin)
                dic_ways[n-coin] = True
        return num_ways

Как видите, n - это сумма. Когда вы сталкиваетесь с суммой, которая была вычислена, вы просто пропускаете ее.