Project Euler Problem 076
Statement
It is possible to write five as a sum in exactly six different ways:
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
How many different ways can one hundred be written as a sum of at least two positive integers?
Solution
This problem is a perfect example of the coin change problem in Dynamic Programming.
Here the different coin values are {1..99} and the value we want to determine in how many ways we can give that change is 100.
The Python implementation for that problem is 6 lines long.
if __name__ == '__main__': ways = [0 for x in range(101)] ways[0] = 1 for coin in reversed(range(1, 100)): for index in range(coin, 101): ways[index] += ways[index - coin] print("The result is:", ways[100])
The Python file is available for download here.
