Рекурсивное решение для запоминания, чтобы решить «подсчет изменений»

Question

Я пытаюсь решить проблему «Подсчета изменений» с запоминанием.

Рассмотрим следующую проблему: Сколько разных способов мы можем изменить на 1 доллар, учитывая полдоллара, кварталы, десять центов, никели и пенни? В более общем смысле, можем ли мы написать функцию для вычисления количества способов изменения любой данной суммы денег, используя любой набор валютных номиналов?

И интуитивное решение с рекурсином.

Количество способов изменить количество, используя n видов монет, равно

1. количество способов изменить количество монет, кроме первого, плюс
2. количествоспособы изменить меньшее количество a - d, используя все n видов монет, где d - номинал монет первого типа.

---

#+BEGIN_SRC python :results output
# cache = {} # add cache 
def count_change(a, kinds=(50, 25, 10, 5, 1)):
    """Return the number of ways to change amount a using coin kinds."""
    if a == 0:
        return 1
    if a < 0 or len(kinds) == 0:
        return 0
    d = kinds[0]　# d for digit
    return count_change(a, kinds[1:]) + count_change(a - d, kinds) 
print(count_change(100))
#+END_SRC
#+RESULTS:
: 292

Я пытаюсь воспользоваться возможностью запоминания,

Signature: count_change(a, kinds=(50, 25, 10, 5, 1))
Source:   
def count_change(a, kinds=(50, 25, 10, 5, 1)):
    """Return the number of ways to change amount a using coin kinds."""
    if a == 0:
        return 1
    if a < 0 or len(kinds) == 0:
        return 0
    d = kinds[0]
    cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
    return cache[a]

Он работает правильно для небольших чисел, таких как

In [17]: count_change(120)
Out[17]: 494

, работает с большими числами

In [18]: count_change(11000)                        
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-18-52ba30c71509> in <module>
----> 1 count_change(11000)

/tmp/ipython_edit_h0rppahk/ipython_edit_uxh2u429.py in count_change(a, kinds)
      9         return 0
     10     d = kinds[0]
---> 11     cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
     12     return cache[a]

... last 1 frames repeated, from the frame below ...

/tmp/ipython_edit_h0rppahk/ipython_edit_uxh2u429.py in count_change(a, kinds)
      9         return 0
     10     d = kinds[0]
---> 11     cache[a] = count_change(a, kinds[1:]) + count_change(a - d, kinds)
     12     return cache[a]

RecursionError: maximum recursion depth exceeded in comparison

В чем проблема с решением для запоминания?

Answer 1

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

def count_change(n, k, kinds):
    if n < 0:
        return 0
    if (n, k) in cache:
        return cache[n,k]
    if k == 0:
        v = 1
    else:
        v = count_change(n-kinds[k], k, kinds) + count_change(n, k-1, kinds)
    cache[n,k] = v
    return v

Вы можете попробовать:

cache = {}
count_change(120,4, [1, 5, 10, 25, 50])

дает 494

, а:

cache = {}
count_change(11000,4, [1, 5, 10, 25, 50])

, выводит: 9930221951