0
$\begingroup$

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.stack.imgur.com/Zx2cG.gif

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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] \}. $

In your specific example:

$$ \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*} $$

Improve this answer
$\endgroup$
6
  • $\begingroup$ Another shoot from the lecture: i.stack.imgur.com/hWqBo.png $\endgroup$
    – mshwf
    Jun 14, 2020 at 2:12
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jun 14, 2020 at 2:31
  • $\begingroup$ Yes, you are right, but unfortunately, it's still the same vagueness. is this formula is for memorization only? can one understand its proof, so if I had a similar problem I can use or develop another formula based on it. I think this is more important than knowing the formula itself. $\endgroup$
    – mshwf
    Jun 14, 2020 at 9:51
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jun 14, 2020 at 10:07
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Jun 14, 2020 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.