In this example I want to show the principles of dynamic programming and recursion in a simple example. Imagine you have coins of different values and you want to count the many ways that those coins can make up 200 pennies/cents. To solve this problem we use a recursive function which grows like a tree. You start with the biggest coins first.

Define a function add() which first loops through all coins. If we have an empty current set or the current coin is less or equal the last coin in the current set, then continue: if the sum of the set plus the proposed coin is less than 200, then add the current coin to the set and pass the new set to add(); if the sum of the set plus the current coin equals 200, add the coin to the set and add the new set to the set of solutions (do nothing if 200 is exceeded). Finally print the length of all solutions which is 73682.

This a recursive setup where add() references itself – you pass a current unfinished set to this function.

Here is the code in Python (v3) – it takes 7 seconds on repl.it.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#as a tree tot = 200 coins = [200, 100, 50, 20, 10, 5, 2, 1] finals = [] #global def add(cur): for c in coins: if cur == [] or c <= cur[-1]: #add same or smaller if sum(cur) + c < tot: cur2 = cur + [c] add(cur2) elif sum(cur) + c == tot: cur2 = cur + [c] finals.append(cur2) add([]) # start with empty set print(len(finals)) |