Memoized implementation of change-making algorithm
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 &lt;= 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 &lt;= 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):          # &lt;== *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 &lt;= W)
    return min(next_iteration, key = len)

return inner(W)


That does seem nicer. I like it.