# Minimization of amount in the change coins problem using the dynamic programing approach

I'm learning the dynamic programming approach to solve the coins change problem, I don't understand the substitution part

Given: amount=9, coins = [6,5,1],

the instructor simplified it with this function:

minCoins = min {(9-6)+1 , (9-5)+1, (9-1) +1} = min{4, 5, 9} = 4

I don't understand the logic of this min method: why we say that to change amount of 9 coins, we can simply, take the minimum of: 9 - {all coins} +1 ?

here's a Gif that visualizes the instructor's approach: https://i.sstatic.net/Zx2cG.gif

(*taken from the Algorithmic Toolbox course/ instructor: Prof. Pavel A. Pevzner)

Your formula is wrong (I would like to see where exactly this formula appears in the course, it is not in the gif you linked).

The correct formula is the following: Let $$n$$ be your amount. Let minCoins be an array of $$n+1$$ elements indexed from $$0$$ to $$n$$, where minCoins$$[i]$$ is the minimum amount of coins needed to give change for the amount $$i$$. Let $$c_1, \dots, c_k$$ be the denominations of coins you have available.

Then minCoins$$[0]=0$$ and, for $$i>0$$: $$\text{minCoins}[i] = \min_{\substack{j=1,\dots,k\\c_j \le i}} \{1 + \text{minCoins}[i-c_j] \}.$$

\begin{align*} \text{minCoins}[9] &= \min \{\text{minCoins}[9-6]+1 , \text{minCoins}[9-5]+1, \text{minCoins}[9-1] +1\} \\ &= \min \{\text{minCoins}[3]+1 , \text{minCoins}[4]+1, \text{minCoins}[8] +1\} \\ &= \min\{ 3+1, 4+1, 3+1\} \\ &= \min\{ 4, 5, 4\} = 4. \end{align*}
• This confirms what I have written. The minimum is not among $(9-6)+1$, $(9-5)+1$, and $(9-1) +1$ but rather among minCoins[9−6]+1, minCoins[9−5]+1, and minCoins[9−1]+1. Commented Jun 14, 2020 at 2:31
• No, the formula works perfectly fine for a "bottom-up" dynamic programming. Start from minCoins[0], whose values is known, and then compute minCoins$[i]$ for $i=1, \dots,n$ in increasing order of $i$ by applying the recursive definition I gave in my answer. Notice that it only depends on values of minCoins$[x]$ for $x<i$, which are all already known at this point. Commented Jun 14, 2020 at 10:07
• The intuition behind the recursive formula is the following: Imagine you are giving change for a (non-zero) amount $i$ by handing out coins. You'll need a coin of some of the available denominations $c_j$ (for simplicity think that is the last coin you are handing out, even though it doesn't really matter). Since you are using $c_j$, the optimal solution will be exactly the minimum amount of coins needed to give change for the remaining amount $i-c_j$, plus 1 (to account for the coin $c_j$ itself). Of course you don't know which coin $c_j$ you should use. Commented Jun 14, 2020 at 10:10