In the United Kingdom the currency is made up of pound (£) and pence (p). 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?
Let \(p\) be the finite sequence \((1, 2, 5, 10, 20, 50, 100, 200)\). Let \(f(n, i)\) be the number of ways to make \(n\) pence out of coins with value no greater than \(p_i\). We can't use negative coins, so \(f(n, i) = 0\) when \(n \lt 0\), and if we can only use pennies then there's only one possible combination, so \(f(n, 1) = 1\) when \(n \geq 0\). Otherwise, we separately count the combinations where at least one coin has value \(p_i\) and the combinations where none do. In the former case, the remaining coins will sum to \(n - p_i\) and may include more coins with value \(p_i\). In the latter case, we're counting coins that sum to \(n\) and have value less than \(p_i\). Thus when \(n \geq 0\) and \(i \geq 2\), we have \(f(n,i) = f(n-p_i,i) + f(n,i-1)\). The problem asks for \(f(200,8)\).
def p31(m=200):
p = [1, 2, 5, 10, 20, 50, 100, 200]
f = [1 for n in range(m+1)]
for i in range(1, 8):
for n in range(p[i], m+1):
f[n] += f[n-p[i]]
return f[m]