test-dollar-change.py

def count_bills(bills, amount):
    result = 0
    bills.reverse()
    for bill in bills:
        result += amount//bill
        amount %= bill
    return result

def count_bills2(bills, amount):
    dp = [0] + [float('inf')]*amount

    for i in range(1, amount+1):
        for bill in bills:
            if bill <= i:
                dp[i] = min(dp[i], dp[i-bill]+1)

    return dp[amount] if dp[amount] != float('inf') else -1


for amount in range(1, 100):
    bills = [2, 5]
    m1, m2 = count_bills(bills, amount), count_bills2(bills, amount)
    if m1 != m2:
        print(amount, m1, m2)