7
Oct

# 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

• nehal choraria says:

Excellent explanation! Thank you!

• Tuấn Anh Đào says:

thank you so much

• Rohaan Joshi says:

What happens when the coin array has only even numbered coins and the value = an odd number??

• Pranto Saha says:

if the supply of coin are limited then who can we find the minimum number of coin ?

• Jay Chou says:

This helped me understand the solution immensely! Awesome!

• k.v.Narasimha Murthy says:

no suprise the dislikes are more you deserved it

• Aayush Gupta says:

use less video

• VergilTheDevil666 says:

Worst way to explain…useless

• Gema Pratama A says:

UNCLEAR

• Pratik Gupta says:

what is the meaning of audio in this..if you are just reading the slides…this was not expected from GeeksforGeeks

• Anand Kulkarni says:

You need to derive that formula coding is the dumb part how that formula was found or derived is the essence

• Izanagi Jun says:

wrong solution, this solution is built on a certain input not general.

• Deepak Atariya says:

I am in love with dynamic programming! thank you so much

• shweta pawar says:

• Anupama Hazarika says:

Geeks for Geeks should maintain their high standards.
This video is pathetic.
Dissapointed

• Divya Nesana says:

Please dont make videos again..this sucks😑

• Vishal Pouras says:

What a useless video, no logic at all, just reading out slides!

• Shreya Birthare says:

came especially to dislike the video for its poor explanation

• Sharath Gowda says:

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

• Yogesh Bagariya says:

Shit

• ak d says:

PATHETIC…AND SPIT OUT THE GUM..

• akash verma says:

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