The following pseudocode finds the smallest number of coins needed to sum upto S using DP. Vj is the value of coin and min represents m as described in the following line.
For each coin j, Vj≤i, look at the minimum number of coins found for the i-Vjsum (we have already found it previously). Let this number be m. If m+1 is less than the minimum number of coins already found for current sum i, then we write the new result for it.
1 Set Min[i] equal to Infinity for all of i
2 Min[0]=0
3
4 For i = 1 to S
5 For j = 0 to N - 1
6 If (Vj<=i AND Min[i-Vj]+1<Min[i])
7 Then Min[i]=Min[i-Vj]+1
8
9 Output Min[S]
Can someone explain the significance of the "+1 " in line 6? Thanks
The +1 is because you need one extra coin. So for example, if you have:
Vj = 5
Min[17] = 4
And you want to know the number of coins it will take to get 22, then the answer isn't 4, but 5. It takes 4 coins to get to 17 (according to the previously calculated result Min[17]=4), and an additional one coin (of value Vj = 5) to get to 22.
EDIT
As requested, an overview explanation of the algorithm.
To start, imagine that somebody told you you had access to coins of value 5, 7 and 17, and needed to find the size of the smallest combination of coins which added to 1000. You could probably work out an approach to doing this, but it's certainly not trivial.
So now let's say in addition to the above, you're also given a list of all the values below 1000, and the smallest number of coins it takes to get those values. What would your approach be now?
Well, you only have coins of value 5, 7, and 23. So go back one step- the only options you have are a combination which adds to 995 + an extra 5-value coin, a combination which adds to 993 + an extra 7-value, or a combination up to 977 + an extra 23-value.
So let's say the list has this:
...
977: 53 coins
...
993: 50 coins
...
995: 54 coins
(Those examples were off the top of my head, I'm sure they're not right, and probably don't make sense, but assume they're correct for now).
So from there, you can see pretty easily that the lowest number of coins it will take to get 1000 is 51 coins, which you do by taking the same combination as the one in the list which got 993, then adding a single extra 7-coin.
This is, more or less, what your algorithm does- except instead of aiming just to calculate the number for 1000, it's aim would be to calculate every number up to 1000. And instead of being passed the list for lower numbers in from somewhere external, it would keep track of the values it had already calculated.