Find minimum number of coins (using Dynamic Programming) | GeeksforGeeks

Find minimum number of coins (using Dynamic Programming) | GeeksforGeeks


Hi friends! Welcome to GeeksforGeeks. In this
video we’ll see how to find the min no of coins that make a given value.
Let’s look at the problem statement. Given a value V, we want to make change for V cents.
We have infinite supply of each of C={ C1, C2, .. , Cm} valued coins
What is the minimum number of coins to make the change? Let’s look at an example
Coins array is 25,10, 5 and value is 30. Output will be 2 We can use one coin of 25 cents
and one of 5 cents Coins array is 9,6,5,1 and value is 11. Output
will be 2 We can use one coin of 6 cents and one coin of 5 cents
Now let’s look at the recursive solution to this problem. The minimum number of coins
for a value V can be computed using this recursive formula.
If V==0, then 0 coins required. If V>0, then the minimum no of coins required
to make value V will be equal to the minimum no of coins required to make value V-coin[i]
+1. Basically coin[i] is the coin whose value is just lesser than V. Let’s look at the
implementation and this will get clear. First we have the base case, if V=0, then
0 no of coins required. We initialise our result as int_max. Then we traverse through
thr cins array and find the coin whose value is just less than V. Then we have our subresult
which is equal to the minimum no. of cons required to make value V-coin[i]. After that,
if result is greater than subres +1. Basically the minimum no of coins required to make the
value V is greater than the min no of coins required ot make the value V-coins[i]+1 then
we set result=subres +1 and also subres shouldn’t be equal to INT_MAX.Basically
we add 1 to the no. of coins required. Let’s look at an illustration and this will be more
clear. The time complexity of this recursive solution will be exponential.
Here’s the illustration. We have the input coins array 9,6,5,1 and we want to make the
value 11. What is the min no of coins required? Initially our result is set to INT_MAX
Next, we traverse through the coins array and chose 9. New value becomes 11-9=2. Subresult
will be the min no of coins required to make value 2., this in turn is min no of coins
required to make value 1+1, which is min no of coins required to make value 0+1. basically
2 can be created if we chose 2 coins of denomination 1. Hence the subresult will be 2, as we’ll
need 2 coins to make the value 2. Subres in this case is going to be 2 and result will
be subres +1=3. Next we traverese further in our denominations
array, we chose value 6. New value becomes 11-6=5. Subresult will be the min no of coins
required to make value 5, result finally is subresult+1. Subres in this case will be 1,
as we can create 5 using 1 coin of denomination 5. So in this case the result willl be 1 +1
=2 We traverse further and chose value 5. New
value will be 6, subresult will be 1. We can use a coin of denomination 5 and denomination
6. So result will be 2 again, but we will not update the result because result is not
greater than subres +1. Similarly, for coin 1, the condition res>sub_res +1 will not
be satisfied and res will continue to be 2. So, finally we have coins array 9,6,5,1, and
value 11. Output will be 2, we need a coin of 6 cents and another of 5 cents.
Now let’s look at the overlapping subproblems property. If we draw the complete recursion
tree, we can observer that many subproblems are solved again and again. For eg, we can
create value 11 by using coins 6 and 5 or, by using a coin of value 6 and 5 coins of
value 1. So, we see the subproblem 6 is called twice.
Optimal substructure property. Optimal solution of the given problem can be obtained by using
optimal solutions of its subproblems. For eg. if we know min no of coins to create value
5 and ue 6 then we can determine the min no of coins to create value 11.
So the min coins problem has both properties: Overlapping Subproblems and Optimal Substructure.
Like other typical DP problems, recomputations of same subproblems can be avoided by constructing
a temporary array table[][] in bottom up manner. Let’s look at the implementation now.
First we create the table array such that table[0]=0 and all the rest are set to int_max.
Then we fill the table, by going from value 1 to v, i.e. index 1 to v and fill the table.
Table[i] denotes the minimum no of coins required to create the value i. then go through all
the coins smaller than i Then using the subres and result logic discussed earlier we fill
our table. I.e. if table[i[>subres +1, then table[i] will be equal to subres +1. Finally
we return table[V]- i.e. the min no of coins to create value V. We have a loop from 1 to
V and another from 0 to m, so the time complexity will be O(mV), Let’s look at an illustration.
We have input coins array is 9,6,5,1 and the value=11. What is the min no of coins required?
Initially, Table[0]=0 and rest all are int_max, denoted using infinity symbol here.
Then we fill the table. The value for table[1]=min no of coins require to make value 1=1+
table[0]=1 and in a similar fashion the table gets filled. Table[2]=table[1] +1. Table[3]=
table[2]+1 table[4]=table[3] +1 and table[5] will be either table[0]+1 if we use 5 or table[4]+1
if we use the coin 1, but we will chose table[0] as per the formula table[i]>subres+1. I.e
table[5] will be 1 as we use a single coin 5 as that gave us a smaller value of table[i].
Similarly, we fill the entire table and the ans will be table[11] which is 2.
So, finally result is 2, we need a coin of 6 cents and another of 5 cents.
Please Like, Comment, Share the Video among your friends.Also, Subscribe if you haven’t
already! Thank you.

9 thoughts on “Find minimum number of coins (using Dynamic Programming) | GeeksforGeeks”

  1. Disappointed very bad gfg dint expect this… U are our first source for any doubts and this is how u clarify it??

  2. The video implementation of geeksforgeeks tutorial is not satisfactory. Please give attention to this part. Thank you.

  3. This video lacks explanation in general. Recursive Solution slide in particular, Implementation slide at 2:00 also, for example what is int m? Illustration slide at 2:50 it would be nice to see what code we're running and maybe what the variables hold, what the stack looks like, something that illustrates what's going on better. I keep hearing things like "We set table[i] = INT_MAX" without explaining what table[i] is, or why we're setting it to INT_MAX. It was frustrating watching this, I don't think I've ever given a thumbs down to an educational video, but it's really quite disappointing.

Leave a Reply

Your email address will not be published. Required fields are marked *