1
$\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?

$\endgroup$
  • $\begingroup$ Dude, at least show the effort of typing the question so that other people can find it in their searches. Or else you could just link to the site where you snagged the screenshot from: algorithms.tutorialhorizon.com/… $\endgroup$ – Abhijit Sarkar Jan 19 at 9:00
5
$\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.

$\endgroup$
  • $\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 Feb 3 '17 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 Feb 3 '17 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 Feb 3 '17 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 Feb 4 '17 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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