Understanding change-making algorithm
algorithm, dynamic-programming, python
Solution
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
Problem
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?