Recursive memoization solutio to solve "count changes"

Question

I am trying to solving the "Counting Change" problem with memorization.

Consider the following problem: How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a function to compute the number of ways to change any given amount of money using any set of currency denominations?

And the intuitive solution with recursoin.

The number of ways to change an amount a using n kinds of coins equals

the number of ways to change a using all but the first kind of coin, plus
the number of ways to change the smaller amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.

#+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

I try to take advantage of memorization,

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]

It works properly for small number like

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

work on big numbers

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

What's the problem with memorization solution?

Good efforts! but few issues, please check stackoverflow.com/questions/1988804/… — sam

Gerard Rozsavolgyi Gerard Rozsavolgyi · Accepted Answer · 2019-10-27T15:50:55

In the memoized version, the count_change function has to take into account the highest index of coin you can use when you make the recursive call, so that you can use the already calculated values ...

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

You can try :

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

gives 494

while :

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

outputs: 9930221951

Recursive memoization solutio to solve "count changes"

1 Answers