#!/usr/bin/env python
# coding: utf-8

# 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])


# In[3]:


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


# In[4]:


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


# 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])


# 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])