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))

possible duplicate of [Is there a decorator to simply cache function return values?](http://stackoverflow.com/questions/815110/is-there-a-decorator-to-simply-cache-function-return-values) — perreal, Dec 23 '13 at 11:45
Since you're calling the function recursively, consider injecting the memoization into the function itself, and call the memoized function recursively, this way you'll reuse existing memoized function results when asking for new values. — Lasse V. Karlsen, Dec 23 '13 at 11:45
@perreal the "duplicate" its fine to understand the idea of it, what I faced with is the approach how to save the repeating values and avoid it. but thanks anyway. — Ofir Attia, Dec 23 '13 at 11:49

score 9 · Answer 1 · answered Dec 23 '13 at 12:38

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).

score 2 · Accepted Answer · answered Dec 23 '13 at 14:17

It's not necessary to write a specialized memorizing decorator when you could just use a generic pre-written one...such as the following straight from the PythonDecoratorLibrary:

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's 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's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

You could then apply it to yourchange()function (or any other, since it's generic) like this:

@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

Ok, thanks, btw I didnt knew I can use that, but before you answered I succeed, look on the EDIT — Ofir Attia, Dec 23 '13 at 15:10
Yes, assigning the result to the name of the original function is what @decorator syntax does for you -- and doing so usually means you don't have to change all your existing calls to the use the modified version with a different name. — martineau, Dec 23 '13 at 15:57

Memoizing Coin Change

2 Answers2

Linked