Reply To: Programming

In fact, here’s an improvement to my previous answer which runs in linear time and constant space.

def ways(target):
    # ways[amount][coin] = number of ways of making amount using only coins with value <= coin
    coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000]
    length = 1 + max(coins)
    ways = [{c: c == coins[0] for c in coins} for _ in range(2 * length)]
    offset = 0

    for amount in range(target + 1):
        if amount - max(coins) - offset >= length:
            offset += length
            ways[:length] = ways[length:]
            ways[length:] = [{c: c == coins[0] for c in coins} for _ in range(length)]
        for prev, coin in zip(coins, coins[1:]):
            ways[amount - offset][coin] = ways[amount - offset][prev]
            if amount >= coin:
                ways[amount - offset][coin] += ways[amount - coin - offset][coin]
    return ways[target - offset][coins[-1]]

It appears that there are 21114405534221677368358438421551668808393848059500 ways of making change for £99,999.99!