# Proving a dynamic programming recurrence for coin exchange correct

Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins.

I came into the following formula:

$$T(n,S) = \begin{cases} T(n-1,S) & \text{if c_n > S}, \\ \min(1+T(n,S-c_n), 1+T(n-1,S-c_n), T(n-1, S)) & \text{otherwise}. \end{cases}$$

The formula feels right to me, however when I try to prove it formally I hit the wall.

Is the formula indeed correct? Can someone guide me how to prove it?

• What is $T(n,S)$ supposed to represent? What have you tried? Where did the formula come from, intuitively? Can you try to prove that it will be correct in all cases, perhaps by breaking things down into multiple cases? We expect you to make a significant effort and to show us your reasoning and identify a specific aspect that you are confused about. "Please check whether my answer is correct" questions are off-topic here, per meta discussions here and here. – D.W. Aug 21 '15 at 21:18
• Also mention whether the coins of type $c_i$ are to be used only once or they can be used multiple times. – CSStudent Aug 21 '15 at 22:05