# Understanding change-making algorithm

### Question

I was looking for a good solution to the Change-making problem and I found this code(Python):

``````target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
for i in range(coin,target+1):
ways[i]+=ways[i-coin]
print(ways[target])
``````

I have no problems understanding what the code literally does,but I can't understand WHY it works. Anyone can help?

1
17
12/28/2016 2:06:20 AM

To get all possible sets that elements are equal to 'a' or 'b' or 'c' (our coins) that sum up to 'X' you can:

• Take all such sets that sum up to X-a and add an extra 'a' to each one.
• Take all such sets that sum up to X-b and add an extra 'b' to each one.
• Take all such sets that sum up to X-c and add an extra 'c' to each one.

So number of ways you can get X is sum of numbers of ways you can get X-a and X-b and X-c.

``````ways[i]+=ways[i-coin]
``````

Rest is simple recurrence.

Extra hint: at the start you can get set with sum zero in exactly one way (empty set)

``````ways = [1]+[0]*target
``````
14
2/21/2013 1:19:24 AM

This is a classical example of dynamic programming. It uses caching to avoid the pitfall of counting things like 3+2 = 5 twice (because of another possible solution: 2+3). A recursive algorithm falls into that pitfall. Let's focus on a simple example, where `target = 5` and `coins = [1,2,3]`. The piece of code you posted counts:

1. 3+2
2. 3+1+1
3. 2+2+1
4. 1+2+1+1
5. 1+1+1+1+1

while the recursive version counts:

1. 3+2
2. 2+3
3. 3+1+1
4. 1+3+1
5. 1+1+3
6. 2+1+2
7. 1+1+2
8. 2+2+1
9. 2+1+1+1
10. 1+2+1+1
11. 1+1+2+1
12. 1+1+1+2
13. 1+1+1+1+1

Recursive code:

``````coinsOptions = [1, 2, 3]
def numberOfWays(target):
if (target < 0):
return 0
elif(target == 0):
return 1
else:
return sum([numberOfWays(target - coin) for coin in coinsOptions])
print numberOfWays(5)
``````

Dynamic programming:

``````target = 5
coins = [1,2,3]
ways = [1]+[0]*target
for coin in coins:
for i in range(coin, target+1):
ways[i]+=ways[i-coin]
print ways[target]
``````