# link: https://projecteuler.net/problem=31

# In England the currency is made up of pound, £, and pence, p, and there are
# eight coins in general circulation:
#
# 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
# It is possible to make £2 in the following way:
#
# 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
# How many different ways can £2 be made using any number of coins?
import copy
coins = [1, 2, 5, 10, 20, 50, 100, 200]

total = 200
# you can get total of 0 by exactly 1 combination - do not take anything
combinations = {0: 1}

for coin in coins:
    for (k, v) in copy.deepcopy(combinations).items():
        for x in range(k+coin, total+1, coin):
            if x in combinations:
                combinations[x] += v
            else:
                combinations[x] = v
print(combinations[total])
