python - Memoizing Coin Change

Question

I want to convert my coin change function to memoized function
to do that, I decided to use dictionary so that a key in my dict will be the coin and the value will be a list that contain all the coins that can change the "key" coin.
what I did is:

def change(a,kinds=(50,20,10,5,1)):
    if(a==0):
            return 1
    if(a<0 or len(kinds)==0):
            return 0

    return change(a-kinds[0],kinds)+change(a,kinds[1:])


def memoizeChange(f):
    cache={}
    def memo(a,kinds=(50,20,10,5,1)):

        if len(cache)>0 and kinds in cache[a]:
            return 1
        else:
            if(f(a,kinds)==1):
                cache[a]=kinds // or maybe cache[a].append(..)
                return cache[a]+memo(a-kinds[0],kinds)+memo(a,kinds[1:])
    return memo

memC=memoizeChange(change)
kinds=(50,20,10,5,1)
print(memC(10,kinds))

I would like to get some suggestions , or maybe there is another way to do that.
thanks.

EDIT
Memoized version:

def change(a,kinds=(50,20,10,5,1)):
    if(a==0):
            return 1
    if(a<0 or len(kinds)==0):
            return 0
    return change(a-kinds[0],kinds)+change(a,kinds[1:])


def memoizeChange(f):
    cache={}
    def memo(a,kinds=(50,20,10,5,1)):
        if not (a,kinds) in cache:
                cache[(a,kinds)]=f(a,kinds)
        return cache[(a,kinds)]
    return memo

change=memoizeChange(change)
print(change(10))

Answer 1

It doesn't answer your question as asked, but if r[0] to r[i] are the number of ways of making change with the first k of your denominations, then r[i+1] is the number of ways of making change with the first k-1 denominations plus r[i-k]. This leads to an elegant solution to the problem you're solving:

def change(total, denominations):
    r = [1] + [0] * total
    for k in denominations:
        for i in xrange(k, len(r)):
            r[i] += r[i - k]
    return r[total]

print change(100, (50, 20, 10, 5, 1))

This approach is discussed in Polya's book "How to solve it". In general, using memoisation to ameliorate recursive solutions is a simple way to code dynamic programming solutions in Python, but my personal opinion is that it's an important skill to be able to drop down a level and figure out exactly how to build the intermediate results in a table in a dynamic programming solution. Often (and exemplified here), the result is faster and way simpler to read (although harder to code in the first place).