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?

Answer 1

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