# 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
• (cont.) So, please edit your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about or by identifying a specific conceptual issue that you are confused about/stuck on. You might also want to use LaTeX here to typeset mathematics in a more readable way and proof-read your post, as I can't quite parse your formula. See here for a short introduction to LaTeX. – D.W. Aug 21 '15 at 21:19
• 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
• They can be used several times, as obviously could be seen from my solution. – Naftaly Aug 21 '15 at 22:06
• Obviously, you use induction. – Raphael Aug 22 '15 at 9:06