Understanding change-making algorithm
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 like3+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 = 5coins = [1,2,3]ways = [1]+[0]*targetfor coin in coins: for i in range(coin, target+1): ways[i]+=ways[i-coin]print ways[target]
The main idea behind the code is the following:"On each step there are ways
ways to make change of i
amount of money given coins [1,...coin]
".
So on the first iteration you have only a coin with denomination of 1
. I believe it is evident to see that there is only one way to give a change having only these coins for any target. On this step ways
array will look like [1,...1]
(only one way for all targets from 0
to target
).
On the next step we add a coin with denomination of 2
to the previous set of coins. Now we can calculate how many change combinations there are for each target from 0
to target
.Obviously, the number of combination will increase only for targets >= 2
(or new coin added, in general case). So for a target equals 2
the number of combinations will be ways[2](old)
+ ways[0](new)
. Generally, every time when i
equals a new coin introduced we need to add 1
to previous number of combinations, where a new combination will consist only from one coin.
For target
> 2
, the answer will consist of sum of "all combinations of target
amount having all coins less than coin
" and "all combinations of coin
amount having all coins less than coin
itself".
Here I described two basic steps, but I hope it is easy to generalise it.
Let me show you a computational tree for target = 4
and coins=[1,2]
:
ways[4] given coins=[1,2] =
ways[4] given coins=[1] + ways[2] given coins=[1,2] =
1 + ways[2] given coins=[1] + ways[0] given coins=[1,2] =
1 + 1 + 1 = 3
So there are three ways to give a change: [1,1,1,1], [1,1,2], [2,2]
.
The code given above is completely equivalent to the recursive solution. If you understand the recursive solution, I bet you understand the solution given above.