Question: 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](http://www.columbia.edu/~cs2035/courses/csor4231.S19/dynamic.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](https://i.stack.imgur.com/H6bFP.png)](https://i.stack.imgur.com/H6bFP.png) 

Does it represent the coins we've already used?

Answer: 
`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`.
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.