Coin replacement

Question

I want to convert my coin change function to memoized function
To do this, I decided to use a dictionary so that the key in my dict is a coin, and the value is a list containing all the coins that can change the “key” coin.
What I've done:

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 this.
thanks.

EDIT
Commemorative 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

No need to write a specialized decorator when you could just use a common pre-written ... for example, the following from PythonDecoratorLibrary :

 import collections import functools class memoized(object): '''Decorator. Caches a function return value each time it is called. If called later with the same arguments, the cached value is returned (not reevaluated). ''' def __init__(self, func): self.func = func self.cache = {} def __call__(self, *args): if not isinstance(args, collections.Hashable): # uncacheable. a list, for instance. # better to not cache than blow up. return self.func(*args) if args in self.cache: return self.cache[args] else: value = self.func(*args) self.cache[args] = value return value def __repr__(self): '''Return the function docstring.''' return self.func.__doc__ def __get__(self, obj, objtype): '''Support instance methods.''' return functools.partial(self.__call__, obj) 

Then you can apply it to your change() function (or any other, since it is shared), for example:

 @memoized 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:]) print(change(10)) # 4 

Answer 2

This does not answer your question as asked, but if r [0] - r [i] is the number of ways to make changes with the first k of your items, then r [i + 1] is the number of ways to make changes with the first k- 1 denominations plus r [ik]. This leads to an elegant solution to the problem you are 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 Polly’s book, How to Solve It. In general, using memoisation to improve recursive solutions is an easy way to code dynamic programming solutions in Python, but my personal opinion is that it is an important skill that allows you to reset the level and determine exactly how to create intermediate results in a table in a dynamic software solution. Often (and illustrated here) the result is faster and easier to read (although it is more difficult to code in the first place).