dc.py

def dpMakeChange(coinValueList,change,mincoins,coinsused):  
    for cents in range(change+1):
        coincount = cents
        newcoin = 1
        for j in [c for c in coinValueList if c <= cents]:
            if mincoins[cents-j] + 1 <coincount:
                coincount = mincoins[cents-j]+1
                newcoin = j
        mincoins[cents] = coincount
        coinsused[cents] = newcoin
    return mincoins[change]


def printcoins(coinsused, change):
    coin = change
    coinlist = []
    while coin > 0:
        thiscoin = coinsused[coin]
        coinlist.append(thiscoin)
        coin = coin - thiscoin
    return coinlist


def Change(coins, amount):
    coinsused = [0]*(amount+1)
    coincount = [0]*(amount+1)
    dpMakeChange(coins, amount, coincount, coinsused)
    return (printcoins(coinsused, amount))


def main():  
    amount = 63
    coins = [1, 5, 10, 21, 25]
    print("They are:")
    print (Change(coins, amount))
main()