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?

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
```

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:

- 3+2
- 3+1+1
- 2+2+1
- 1+2+1+1
- 1+1+1+1+1

while the recursive version counts:

- 3+2
- 2+3
- 3+1+1
- 1+3+1
- 1+1+3
- 2+1+2
- 1+1+2
- 2+2+1
- 2+1+1+1
- 1+2+1+1
- 1+1+2+1
- 1+1+1+2
- 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]
```

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow