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.