Project Euler Problem #31:

Problem #31 is one of the many Project Euler problems that can be efficiently solved with Dynamic Programming. The question reads:

Project Euler Problem 31: Coin sums
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:

1x£1 + 1x50p + 2x20p + 1x5p + 1x2p + 3x1p

How many different ways can £2 be made using any number of coins?

The most obvious way to approach this question is by using casework. In fact, this is the solution I initially used when approaching this question. Here was my original solution:

Solution #1: Casework on Largest Coins Approach

We begin by doing casework on the number of £2 coins. For each case, we do casework on the number of £1 coins. For each sub-case, we do casework on the number of 50p coins. This can easily be iterated through recursion by dropping the largest coin at the call of each recursive layer. Here is an implementation of this method in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Recursive Approach to Project Euler Problem #31
 '''

 import time

 def projectEulerProblemThirtyOne(n, currencies):
     currencies = sorted(currencies)[::-1]
     if(len(currencies)==1):
         if(n%currencies[0]==0):
             return 1
         else:
             return 0
     total = 0
     current = currencies[0]
     rest = currencies[1:]
     i = 0
     while(i*current<=n):
         total+=projectEulerProblemThirtyOne(n-i*current, rest)
         i+=1
     return total

 start = time.time()
 print projectEulerProblemThirtyOne(200, [1,2,5,10,20,50,100,200])
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 73682
 --- 0.0563788414001 seconds ---

 for input of n=200, currencies = [1,2,5,10,20,50,100,200]
 '''

As shown above, this approach is quite efficient for small inputs such as n = 200p. However, for larger inputs this solution becomes inefficient quite quickly. Luckily, we can use dynamic programming to make this much more efficient. Here is a dynamic approach that I found in Project Euler’s documentation on this question:

Solution #2: Dynamic Approach

We approach the problem dynamically by storing the number of possibilities for every amount between 0p and 200p and building the answers for larger amounts off of the answers for smaller amounts. This would normally cause a problem if we started with the largest currencies, but by starting with the smallest currencies and checking each currency one at a time, we do not have to worry about unnecessary ordering adding to our count. This approach came entirely from Project Euler’s documentation on this problem. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Project Euler (with Python 2.7 implementation by Walker Kroubalkian)
 Very Dynamic Approach to Project Euler Problem #31
 '''

 import time

 def projectEulerProblemThirtyOne(coins, amount):
     ways = [0]*(amount+1)
     ways[0] = 1
     for i in range(len(coins)):
         for j in range(coins[i], amount+1):
             ways[j] = ways[j] + ways[j-coins[i]]
     return ways[amount]

 start = time.time()
 print projectEulerProblemThirtyOne([1, 2, 5, 10, 20, 50, 100, 200], 200)
 print ("--- %s seconds ---" % (time.time()-start))

 '''
 Prints

 73682
 --- 7.15255737305e-06 seconds ---

 for input of n=200, currency = [1,2,5,10,20,50,100,200]
 '''

As shown above, dynamic approaches can be much more efficient than their recursive counterparts. As stated before, this solution was found in Project Euler’s documentation for this problem, and I take no credit in finding it.

Thanks for reading!