Coin change problem, dynamic.

coin_change.py

def make_change(cents_needed, coin_vals):
    min_coins = [[0 for j in range(cents_needed + 1)]
                for i in range(len(coin_vals))]
    min_coins[0] = range(cents_needed + 1)

    for i in range(1, len(coin_vals)):
        for j in range(0, cents_needed + 1):
            if j < coin_vals[i]:
                min_coins[i][j] = min_coins[i-1][j]
            else:
                min_coins[i][j] = min(min_coins[i-1][j],
                                      1 + min_coins[i][j - coin_vals[i]])

    return min_coins


if __name__ == '__main__':

    min_coins = make_change(30, [1, 10, 25])

    for row in min_coins:
        print row

    print min_coins[-1][-1]