# Printing actual solutions for the coin exchange problem

As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight about it. Specifically, the following implementation of a tabulated-DP-based solution for this problems is presented as follows:

def count(S, m, n ):
# If n is 0 then there is 1
# solution (do not include any coin)
if (n == 0):
return 1
# If n is less than 0 then no
# solution exists
if (n < 0):
return 0;
# If there are no coins and n
# is greater than 0, then no
# solution exist
if (m <=0 and n >= 1):
return 0
# count is sum of solutions (i)
# including S[m-1] (ii) excluding S[m-1]
return count( S, m - 1, n ) + count( S, m, n-S[m-1] );


However, this only counts the number possibles solutions.

Question: How can I actually save these solutions for post-processing?

Previous research: In this very helpful video: https://www.youtube.com/watch?v=ENyox7kNKeY they explain how to use an array of parent pointers, to generate the actual solutions, however, I am having issues with implementing this approach with the previous tabulated solution. Any hint?

• It is not clear the problem you want to solve. Do you want the minimum number of coins to achieve a specific value? – Daniel Saad Jan 24 '18 at 12:03

Assuming that you want the minimum number of coins to achieve a desired value and that you have a sufficient number of coins of every value we have this relation of recurrence:

Let $$S(i,k)$$ be the minimum number of coins to achieve the value $$k$$ considering the first $$i$$ coins. Also, let $$V[i]$$ be the value of the $$i$$-th coin.

So:

$$S(i,k) = \begin{cases} 0 & i = 0 \land k = 0\\ -\infty & i = 0 \land k > 0\\ S(i-1,k) & i > 0 \land V[i-1]-k < 0\\ \max(S(i-1,k),S(i,k-W[i-1])) + 1 & \text{otherwise} \end{cases}$$

• Case 1 = Base case, considering the first 0 coins and the value 0 you pay 0 coins.
• Case 2 = Base case, considering the first 0 coins and a value greater than 0 you cant pay the value.
• Case 3 = Considering the first $$i$$ coins you can pick the solution to pay the value $$k$$ without considering the $$i$$-th coin, which is in $$S(i-1,k)$$.
• Case 4 = Considering the first $$i$$ coins, you should maximize between the solutions considering the $$i$$-th coin and not considering it. If the i-th coin is considered, you increment the number of coins in the solution, because you used the $$i$$-th coin.

A recursion based solution follows in verbatim from this relation of recurrence, but in Dynamic Programming you will replace a recursive call by a table lookup. So basically, where is $$S(a,b)$$ you will replace by a table access $$S[a,b]$$.