# 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.

Excellent explanation! Thank you!

thank you so much

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

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

This helped me understand the solution immensely! Awesome!

no suprise the dislikes are more you deserved it

use less video

Worst way to explain…useless

UNCLEAR

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

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

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

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

why u just reading ? we can read that tho!

Geeks for Geeks should maintain their high standards.

This video is pathetic.

Dissapointed

Please dont make videos again..this sucks😑

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

came especially to dislike the video for its poor explanation

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

Shit

PATHETIC…AND SPIT OUT THE GUM..

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

What is this? Worst explanation ever!

can anyone explain this dynamic method more clearly..i cant understand properly…

Most shittiest explanation ever

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.

Pathetic!

crap