3
$\begingroup$

I'm trying to wrap my head around the coin change problem, where you try to find the total number of ways $N$ cents can be exchanged using $M$ coins $\{C_1, C_2, ..., C_m\}$.

The recurrence relation is this:

recursion

I'm having difficulty understanding the 3rd line where it says solution[i][j-v[i-1]]. What exactly is this v they are talking about? I understand it's just the array index above the current one being worked on, but I still don't get what this v is. Can anybody explain please?

Improve this question
$\endgroup$
1
  • $\begingroup$ We require that you provide proper attribution for all sources where you use copied material. See cs.stackexchange.com/help/referencing. It appears this image was a screenshot taken from algorithms.tutorialhorizon.com/…. Please edit the question to credit the source. Also, we normally prefer that you transcribe text and mathematics instead of using an image for it. You can use LaTeX for that. $\endgroup$
    – D.W. ♦
    Commented Dec 22, 2019 at 19:24

1 Answer 1

Reset to default
8
$\begingroup$

For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$.

Whenever confronted with a new dynamic programming problem, you should always try to understand how optimal solutions are structured in terms of optimal solutions for smaller subproblems (cf. optimal substructure). This will help you come up with the recurrence relation. Note that, in dynamic programming, you take the solution for one or more subproblems (initially, the base cases) and extend them, repeating this extension iteratively until, eventually, you reach the solution for the original problem.

In the coin change problem (using your notation) a subproblem is of the form solution[i][j], which means: you can make change for $j$ cents using the first $i$ coins from $V$. How have we arrived at this optimal solution (i.e., how have we extended a previously solved subproblem)? We may have brought one more coin from $V$ into the picture. How does this new coin extend the previous solution? Well, there are two possibilities: we have used this coin to make change or we haven't. We must add up these two cases (since both of them represent valid ways to make change):

  • Case 1 (the coin is not taken): when coin $i$ is not taken, the number of ways to make change for $j$ is exactly the same as it was before coin $i$ was even considered; that is, solution[i-1][j].

  • Case 2 (the coin is taken): when coin $i$ is taken, your are spending its value; therefore, you must substract the value $C_i$ to $j$. Now, the number of ways to make change is solution[i][j-v[i]] *.

The final recurrence is obtained by adding up these two cases:

solution[i][j] = solution[i-1][j] + solution[i][j-v[i]]

Observe that case 2 is not applicable when $j$ is smaller than the value of the $i$th coin (that is, when $j < C_i$), hence the distinction in the third and fourth lines of your recurrence.

Footnote:

* It will be v[i-1] if the array starts at index 0.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Re your edit to the question, thanks for improving the formatting but there's no need to change "I'm" to "I am" or "its" to "it is". I accepted the edit, but we do prefer to respect the writing style of the original author as long as it doesn't interfere with understanding. (Correcting bad English is fine but contractions aren't bad or even particularly informal.) $\endgroup$
    – David Richerby
    Commented Feb 3, 2017 at 10:27
  • 1
    $\begingroup$ Contractions are slightly informal but I'd be happy to write things like "doesn't", "can't", "isn't" or "it's" in an academic paper. ("I'm" and so on aren't likely to come up.) And I don't think we need to be particularly formal here. :-) $\endgroup$
    – David Richerby
    Commented Feb 3, 2017 at 11:11
  • $\begingroup$ @Mario Cervera: should it not be solution[i-1][j-v[i]], if you can only use the coin once? From the question that is not clear. $\endgroup$
    – noman pouigt
    Commented Feb 3, 2017 at 17:50
  • $\begingroup$ @nomanpouigt: yes, that would be the case if coins could only be taken once. However, due to the recurrence posted by the author of the question, I assumed that the different coin values $\{C_1, C_2, ..., C_m\}$ are infinitely available . $\endgroup$
    – Mario Cervera
    Commented Feb 4, 2017 at 1:05

Your Answer

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

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