A dynamic programming attempt to make change

make_change.py

def make_change(change, denominations=None):
    """
    Given an integer amount of change and a list of denominations of coins
    you can use to make it, return the least amount of coins to make change
    :param change:
    :param denominations:
    :return:
    """
    if denominations is None:
        # start with some sensible (American) defaults
        denominations = [1, 5, 10, 25]
    # this will hold what coins are used for making change for a specific value
    # or rather their indexes in the denominations array
    index = [-1 for _ in range(change + 1)]
    # This will hold the minimum number of coins needed to make change for every
    # value from 0 to n, given our denominations. Initialize all variables as infinity
    # for easier implementation. Could be initialized with -1, but that requires an
    # extra check in the body
    num_coins = [inf for _ in range(change + 1)]
    num_coins[0] = 0  # The first element represents 0 change, so we need 0 coins
    # To find the minimum change, we must first make change for
    # every value from 0 to change using the coins
    for j, coin in enumerate(denominations):
        # for every coin denomination, attempt to make change
        # for every value between 0 and change
        for i in range(change + 1):
            # is it cheaper to use the current number of coins or
            # can we use a previous value offset by the value of the
            # current denomination?
            t = min(num_coins[i], num_coins[i - coin] + 1)
            # if there was a new minimum value, we need to update
            # the index to point to the new denomination for this value
            if t != num_coins[i]:
                index[i] = j
            num_coins[i] = t

    return {"denominations": denominations, "index": index, "num_coins": num_coins}


def print_change(change, index, denominations=None):
    """
    Given an integer value of change to be made and pre-computed indexes for
    said change, print the coins needed to make said change
    :param change: The integer value of change to make
    :param index: Precomputed index array from the ``make_change`` method
    :param denominations: If not given, will be defaulted to [1,5,10,25]
    :return: 
    """
    if denominations is None:
        # start with some sensible (American) defaults
        denominations = [1, 5, 10, 25]
    # we start with no coins
    coins = {}
    # While there are coins to make change with
    while index[change] >= 0:
        # get the current denomination value we're working with
        current_coin = denominations[index[change]]
        # default check for non-existent dictionary keys
        if coins.get(current_coin, 0) == 0:
            coins[current_coin] = 1
        else:
            coins[current_coin] += 1
        # Subtract the current denomination value from the change
        # to move on and find the next coin needed
        change -= current_coin

    print "To make change for {change} you need: ".format(change=change)
    for k, v in coins.iteritems():
        print "{num_coins} of the {denomination} coins".format(num_coins=v, denomination=k)