Reply To: Programming

Re @ByteInBits Question #3

Here’s a Python solution, which outputs 4563.
It iterates over target amount, rather than actual sets of coins, so there’s no first/last sets.

target = 100
current = 0
coins = [ 1, 2, 5, 10, 20, 50, 100 ]
# ways[amount][coin] = number of ways of making amount using only coins with value <= coin
ways = [{c: 0 for c in coins} for amount in range(target + 1)]

while current != target:
    current += 1
    ways[current][1] = 1
    for prev, coin in zip(coins, filter(lambda c: c > 1, coins)):
        for count in range((current // coin) + 1):
            ways[current][coin] += max(1, ways[current - count * coin][prev])
print(ways[target][coins[-1]])