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.

StackExchange Code Review Q#104830, answer score: 5