What does the +1 mean in the recurrence relation for the coin change problem (dynamic programming approach)?

1
votes

I was seeing the Coin Change problem. In general, the input is n (the change to be returned) and the denominations (values of coins in cents) available, v1 < v2 < v1 < ... < vk; the goal is to make the change for n cents with the minimum number of coins.

I was reading this pdf from Columbia university, but I don't get why, at slide number 6, we have a +1 in the recurrence relation:

enter image description here

Does it represent the coins we've already used?

2
algorithmdynamic-programminggreedycoin-change
It represents the coin whose value is x, found in one step of the algorithm. - Welbog
Well the relation is C[p] = 1+C[p-x] it means that the number of coins to obtain a value p is one plus the number of coins to generate C[p-x] if we add a coin x, so the +1 simply is used to "increment" the number of coins. - Willem Van Onsem
Why can't the recurrence relation be C[p] = p//x + C[p mod x] where // is integer floor division. - Anthony O

2 Answers

1
votes

C[p] indicates the minimum number of coins you to build denomination p from your available coins array d.

So to create such sum you must pick coins d[i] such that d[i]<p.

Let's assume that you picked a coin d[i] from d. Which means you coin count now is one.

Now to make the sum p, collect more coins for a sum p-d[i].

But you already did have min_coins needed for making sum p-d[i] in C[p-d[i]].

Which means one possible coin count for making sum p is 1+C[p-d[i]].

But there could be multiple denominations where d[i]<p possible, then you have to pick the one which results you with minimum, which is exactly what that you function is doing.

This way you can understand that +1 in function as a first coin that we are considering for making the sum p.

0
votes

Suppose my denominations look like this: d = [1, 5, 10, 25]. Let's also suppose n, the change to be returned, is 26. This means that:

C[26] = min{C[26 - d[i]] + 1}

which can be expressed as:

C[26] = min{C[25], C[21], C[16], C[1]} + 1.

The "+1" here is just the coin you need to add to one of the previously-solved subproblems (e.g. C[25], C[21]) to get C[26].

If we consider an even simpler example, like n = 6 with the same denominations, we know that the recurrence will be:

C[6] = min{C[6 - d[i]]} + 1

or:

C[6] = min{C[5], C[1]} + 1

We know that C[5] is 1 (because the minimum way to make 5 cents with a denomination of 5 in the mix is 1) and similarly C[1] = 1. The minimum here is just 1, so 1 + 1 = 2 and the minimum number of coins needed to make 6 cents is 2 coins.