In [50]: 
def exhaustiveChange(amount, denominations):
    bestN = 100
    count = [0 for i in xrange(len(denominations))]
    while True:
        for i, coinValue in enumerate(denominations):
            count[i] += 1
            if (count[i]*coinValue < 100):
                break
            count[i] = 0
        n = sum(count)
        if n == 0:
            break
        value = sum([count[i]*denominations[i] for i in xrange(len(denominations))])
        if (value == amount):
            if (n < bestN):
                bestN = n
    return bestN
In [52]: 
%timeit exhaustiveChange(42, [25,20,10,5,1])

1 loops, best of 3: 1.05 s per loop
In [53]: 
def branchAndBoundChange(amount, denominations):
    bestN = amount
    count = [0 for i in xrange(len(denominations))]
    while True:
        for i, coinValue in enumerate(denominations):
            count[i] += 1
            if (count[i]*coinValue < amount):
                break
            count[i] = 0
        n = sum(count)
        if n == 0:
            break
        if (n > bestN):
            continue
        value = sum([count[i]*denominations[i] for i in xrange(len(denominations))])
        if (value == amount):
            if (n < bestN):
                bestN = n
    return bestN
In [54]: 
%timeit branchAndBoundChange(42, [25,20,10,5,1])

100 loops, best of 3: 13.2 ms per loop
In [55]: 
def RecursiveChange(M, c):
    if (M == 0):
        return [0 for i in xrange(len(c))]
    smallestNumberOfCoins = M+1
    for i in xrange(len(c)):
        if (M >= c[i]):
            thisChange = RecursiveChange(M - c[i], c)
            thisChange[i] += 1
            if (sum(thisChange) < smallestNumberOfCoins):
                bestChange = thisChange
                smallestNumberOfCoins = sum(thisChange)
    return bestChange
In [58]: 
%timeit RecursiveChange(42, [25,20,10,5,1])

1 loops, best of 3: 883 ms per loop
In [59]: 
def DPChange(M, c):
    change = [[0 for i in xrange(len(c))]]
    for m in xrange(1,M+1):
        bestNumCoins = m+1
        for i in xrange(len(c)):
            if (m >= c[i]):
                thisChange = [x for x in change[m - c[i]]]
                thisChange[i] += 1
                if (sum(thisChange) < bestNumCoins):
                    change[m:m] = [thisChange]
                    bestNumCoins = sum(thisChange)
    return change[M]
In [60]: 
%timeit DPChange(42, [25,20,10,5,1])

1000 loops, best of 3: 207 µs per loop
In [38]:
In []: