TheAlgorithms-Python
59 строк · 1.5 Кб
1"""
2Problem 31: https://projecteuler.net/problem=31
3
4Coin sums
5
6In England the currency is made up of pound, £, and pence, p, and there are
7eight coins in general circulation:
8
91p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
10It is possible to make £2 in the following way:
11
121×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
13How many different ways can £2 be made using any number of coins?
14
15Hint:
16> There are 100 pence in a pound (£1 = 100p)
17> There are coins(in pence) are available: 1, 2, 5, 10, 20, 50, 100 and 200.
18> how many different ways you can combine these values to create 200 pence.
19
20Example:
21to make 6p there are 5 ways
221,1,1,1,1,1
231,1,1,1,2
241,1,2,2
252,2,2
261,5
27to make 5p there are 4 ways
281,1,1,1,1
291,1,1,2
301,2,2
315
32"""
33
34
35def solution(pence: int = 200) -> int:
36"""Returns the number of different ways to make X pence using any number of coins.
37The solution is based on dynamic programming paradigm in a bottom-up fashion.
38
39>>> solution(500)
406295434
41>>> solution(200)
4273682
43>>> solution(50)
44451
45>>> solution(10)
4611
47"""
48coins = [1, 2, 5, 10, 20, 50, 100, 200]
49number_of_ways = [0] * (pence + 1)
50number_of_ways[0] = 1 # base case: 1 way to make 0 pence
51
52for coin in coins:
53for i in range(coin, pence + 1, 1):
54number_of_ways[i] += number_of_ways[i - coin]
55return number_of_ways[pence]
56
57
58if __name__ == "__main__":
59assert solution(200) == 73682
60