# Memoized implementation of change-making algorithm

Recently, I wrote a simple program to solve the change-making problem. Rather than the tabular dynamic programming solution (described in the link), I tried to write a solution that uses memoization.

usd = [25, 10, 5, 1]

def make_change(W, denoms=usd):
"""
Solves the change-making problem where W is
a given amount of money and denoms
is a list of the denominations available

>>> make_change(6,[3,1])
(3, 3)
"""

d = {}

def inner(W, sol):
if W == 0:
return sol

if W in d:
return d[W]

tmp = []
for coin in denoms:
w = W - coin

if w >= 0:
tmp.append(inner(w, sol + (coin,)))

d[W] = min(tmp, key=lambda x : len(x))
return d[W]
return inner(W, tuple())

if __name__ == "__main__":
import doctest
doctest.testmod()


I'm wondering if there's a better way I should be doing the memoization (i.e. a decorator):

def memoize(f):
d = {}
def inner(args):
if args not in d:
d[args] = f(*args)
return d[args]
return inner


The above code caches the arguments so they don't get recomputed in future computations. Here, however, I think we only want to cache the solution for a given W, and I'm not sure a general purpose decorator like the one above is necessarily correct.

I'd say the main issue with your code is that you're confusing what the inner function is supposed to do:

def inner(W, sol):
if W == 0:
return sol   ## return result so far?

if W in d:
return d[W]  ## return best result for W?


Those are two different kinds of values. If you're just returning "smallest tuple for weight W", then W == 0 should yield tuple(). And your recursive step should just be:

tmp.append(inner(w) + (coin,))


With that, I would rename tmp. It's not really a temporary variable, we're actually building up our next possible step. So really something like:

next_iteration = (inner(W - coin) + (coin,)
for coin in denoms
if coin <= W)


And for your key argument to min, you need a function taking one argument and returning a value. You had:

key = lambda x: len(x)


But lambda x: len(x) is the same as len. So I'd reduce the whole thing to:

d = {0: tuple()} # to avoid the special case of 0
def inner(W):
if W in d:
return d[W]

next_iteration = (inner(W - coin) + (coin,)
for coin in denoms
if coin <= W)
d[W] = min(next_iteration, key=len)
return d[W]

return inner(W)


For memoize, sure, with one minor modification:

def memoize(f):
cache = {}                 # why d?
def inner(*args):          # <== *args, not args
if args not in cache:
cache[args] = f(*args)
return cache[args]
return inner


And then just:

@memoize
def inner(W):
if W == 0:
return tuple()

next_iteration = (inner(W - coin) + (coin,)
for coin in denoms
if coin <= W)
return min(next_iteration, key = len)

return inner(W)


That does seem nicer. I like it.

• I like this too, just replace the [ with ( for lazyness and efficiency. (see: python.org/dev/peps/pep-0289 ) – Caridorc Sep 16 '15 at 18:40

Be careful with using lists as default values for functions. In your case you don't modify denoms, but when default value lists or dictionaries are modified it's actually preserved from one function call to another. For example:

nums = [2, 5]

def f(vals=nums):
vals.append(12)
print vals


Calling f repeatedly will produce this:

>>> f()
[2, 5, 12]
>>> f()
[2, 5, 12, 12]
>>> f()
[2, 5, 12, 12, 12]


Even though your current code doesn't run into that trouble you can easily avoid accidentally creating these issues by making usd a tuple. Tuples can't be modified so if you just set usd as one you couldn't even accidentally modify it.

usd = (25, 10, 5, 1)


Also don't use W just because the algorithm does. total, total_change or total_money are all better candidates to choose and clearer to understand. Likewise with d and sol.