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