Coin change - DP

问题:

I have a small problem understanding the coin change problem in dynamic programming. Simply put, I have to change a sum using a minimum number of coins.

I have n denominations of coins of values 1 = v1 < v2 < ... < vn, and we note M(j) the minimum number of coins required to make change for amount j.

In the above formula I don't understand what M(j-vi) means. vi has to be the maximum value of the coins used in j-1?

回答1:

You're making piles of coins for different values j, named M(j). The point of M(j - v_i) is to consider a coin of value v_i, then which pile do you add it to in order to reach the value j? The pile with value j - v_i of course, because that plus the coin you're considering now add up to the value j.

Of course the goal is to have as few as possible coins, so you take the smallest pile that you can extend to reach the value j by adding a coin of v_i to it. That's what the min does. +1 because you add the coin v_i to the pile to form the new pile M(j).

回答2:

Plus one means you are consuming one more coin and therefore the total change you will make is decrease by the amount of the added coin, which is why the original j value is decremented.