In [1]:

import numpy
def changeDp(money, coins):
    D = numpy.zeros((len(coins), (money + 1)), dtype = int)
    # Initialize first row of the matrix
    D[0,1:] = range(1, money + 1)
    for i in range(1, len(coins)):
        for j in range(0, money + 1):
            if j < coins[i]:
                D[i,j] = D[i-1,j]
            else:
                D[i,j] = min(D[i-1,j],
                            D[i,j - coins[i]] + 1)
    return D[-1][-1]

In [2]:

changeDp(12, [1,4,5])

Out[2]:

In [3]:

coins = [50,25,20,10,5,1][::-1]
changeDp(40, coins)

Out[3]:

In [4]:

coins = [1,3,5,11,20,21,22]
changeDp(16164, coins)

Out[4]:

In [5]:

import numpy
def changeDp(money, coins):
    D = numpy.zeros((len(coins), (money + 1)), dtype = int)
    # Initialize first row of the matrix
    D[0,1:] = range(1, money + 1)
    for i in range(1, len(coins)):
        for j in range(0, money + 1):
            if j < coins[i]:
                D[i,j] = D[i-1,j]
            else:
                D[i,j] = min(D[i-1,j],
                            D[i,j - coins[i]] + 1)
    return D

In [6]:

changeDp(20, [2,3])

Out[6]:

array([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16,
        17, 18, 19, 20],
       [ 0,  1,  2,  1,  2,  3,  2,  3,  4,  3,  4,  5,  4,  5,  6,  5,  6,
         7,  6,  7,  8]])

In [9]:

def DPChange(money,coins):
    MinNumCoins = {}
    MinNumCoins[0] = 0
    for m in range(1,money+1):
        MinNumCoins[m] = float('inf')
        for i in range(len(coins)):
            if m >= coins[i]:
                if MinNumCoins[m-coins[i]] + 1 < MinNumCoins[m]:
                               MinNumCoins[m] = MinNumCoins[m-coins[i]] + 1
    return MinNumCoins

In [13]:

DPChange(20, [2,3])

Out[13]:

{0: 0,
 1: inf,
 2: 1,
 3: 1,
 4: 2,
 5: 2,
 6: 2,
 7: 3,
 8: 3,
 9: 3,
 10: 4,
 11: 4,
 12: 4,
 13: 5,
 14: 5,
 15: 5,
 16: 6,
 17: 6,
 18: 6,
 19: 7,
 20: 7,
 21: 7,
 22: 8,
 23: 8,
 24: 8}