Coin Change Problem Number of ways to get total | Dynamic Programming | Algorithms

particular topic on the basics of dynamic programming so I'll provide you the link in the description box you can check it out now the coin exchange problem is also of two types one type of problem we will discuss in this video and second type of problem we'll discuss in next video fine so the problem is you are given different types of coins where you can say a coins of different denominations like one rupee coin 2 rupee coin 5 rupee coin 10 rupee note 10 rupee coin something like this and you are given a certain amount fine now the question is or the problem is you have to find out in how many ways or you can say the total number of ways you have to find out in which you can make the change of the given amount using the given coins see let us take one example coins are given one two and three denomination of one two and three and here here say the condition is you have infinite supply of coins that is very important here the condition is in finite supply of coins you have fine the nomination of one denomination to denomination through you are having coins of these denomination and the amount given is suppose five let us take an example you went to a shop and you maybe bought something and in Britain in return maybe a shopkeeper has to give you five rupees but he is not having a five through peak while he is having only one rupee coin 2 rupee coin and see all the practically it is not possible to Hobbs rupee coin but when they are solving this type of question then we assume we have one rupee coin 2 rupee coin 7 doping 10 rupee and something like this fine now how he can give you 5 rupees using these coins and the condition is he is having infinite supply of coins so first first thing is he can give you 5 one rupee coin that is fine 1 1 1 in one second ways he can give you three one rupee coin and one 2 rupee coin the total is 5 2 1 2 3 4 5 that is also fine our third ways he can give you maybe one one rupee coin and 2 2 rupee coin that is also 5 that this this also makes a total of 5 2 plus 2 plus 1 that is 5 or another pieces maybe he can give you 1 1 2 1 rupee coin and 1 3 rupee coin that is also will make a total of 5 3 plus 4 plus 1 that is 5 or another way is maybe he can give you 1 2 rupee coin and 1 3 rupee coin now I guess there is no way he can give you these coins to make a total of 5 so total ways our total ways to make this sum using these coins is 1 2 3 4 & 5 ways now we'll solve we'll take one more example and we'll solve that problem using dynamic programming see one is this kind of problem I have already told you there are two types of coin change problem one is this kind of problem you have to find out total number of ways second problem is coins are given different denomination of coins are given certain amount is given you have to find out the minimum number of coins to make this this amount using these coins so if if we will show that problem using the same example then suppose coins are 1 2 3 total is 5 now you have to find out the minimum number of coins to make the sum now if we choose this set then how many coins we need to make this 5 1 2 3 4 5 5 one rupee coin fine if we choose this way then how many coins you need to make a sum of 5 1 2 3 4 4 points 3 1 rupee coin and 1 2 rupee coin something like this now out of these ways minimum of coins are this one if you choose this set to coins you need to make this total second problem is something like this you have to find out minimum number of coins well but in this video I'm going to tell you how to calculate the total number of ways in next video we'll discuss how to calculate minimum number of coins so let us take this example we are given the squares of denomination 2 3 5 and and and the amount given is 15 now you have to find out the total number of ways in which you can make a change of this amount using these coins and the condition is you are given infinite supply of coins right now using dynamic programming how to calculate this thing see we will we can use recursion also but what does the drawback of using recursion that we have discussed in previous video fine because the time complexity would be exponential 2 raised to power and and why so because the subproblems are computed and gaen and again they are not going to store the result but if you use dynamic programming that will store the intermediate result and we will use those results whenever the same sub problem comes in future that is why dynamic programming will take less time okay a number of computations will be for less obviously now see how to how to solve this problem using dynamic programming we are going to generate a table by so because we are going to store the results in that table so that we can easily use those results those intermediate results fine so this way we will we are going to write the coins the denomination of coins we are having 2 3 5 and 10 right generally we write these denomination in that ascending order okay and this way this way in this this side we are going to use this amount but will not write 15 here because we are going to divide this problem in dynamic programming we are going to divide the complex problem into subproblems so we are going to divide this sum into smaller sums so we are going to start from 0 and till 15 we will write here okay 0 then 1 now we have divided this complex problem to Smith sampler sub-problems like from zero to 15 you can take it this one suppose at time when we we are supposed to make the change of this amount one using these coins at some point of time we are going to make a change for this amount using these number of coins and ultimately we will reach to solution of the complex problem okay so here 3 simple steps are there first as exclude the coin next is include that new coin or third is add this first and second now how to use these steps I will show you in this case at starting suppose we are we are at eye eye when you suppose this side as we are taking I value this side we are taking J value okay now when we have only coins of denomination 2 and the sum is 0 you have to make this sum is there any way yes there is a way one way and which is that way because if you do not choose this coin this coin of this denomination then obviously you will make some of 0 now don't use any point so there is one way so in this column we always write 1 1 1 below this 0 fine because if you do not use if we do not choose any coins then obviously we are going to make a sum of 0 now that is why we are taking here 1 now come to this mind now the sum is 1 can you make this sum using a coin of denomination - you can't fine so here you will write what 0 okay now next test - now see some is 2 and you how to make this sum using a coin of denomination - is there a way yes we can do if we choose 1 2 rupee coin then obviously we can take some of tuna so that is why we have one way can you make a sum of 3 using coin of denomination - if you choose one two rupee coin then you cannot make if Totoro Pico and then also some is for you cannot get three in any case so there is no way okay simply you will write some you can make this for yes we can make only one way we have which way is this 2 + 2 - 2 rupee coin you chose and you will make a song for so that is why we are we are having only one way can you make the sum 5 no can you make this yes thus no this is 0 1 0 1 0 1 & 0 fine now I value is increased we are having now points of denomination 2 & 3 now the new coin is this 3 fine now here we are using this rule but simple rule is so you can say the shortcut is if this if coin value is greater than the Sun then just copy the above value this is the simple trick if this coin value this coin value is greater than the sum value then simply just copy the above value okay this is the simple rule so coin value is now 3 here if we have already taken 1 is less than 3 so we simply copy over this value from the above said here we copy this value fine here is 1 here also we have 1 but now when sum is 3 now this 3 coin value is 3 sum is also 3 so this condition is not true now you cannot copy the above value you have to calculate that value now to calculate this value you have to follow these rules first is if you do not include this coin then how many ways are there to make a sum of 3 just check the value of the above self 0 ways so you write 0 plus if you include this point if you include then how many ways are there how to calculate that thing if you are including that coin just then you have to do this one thing just reduce this coin value from the amount we are calculating value for this cell now check out this amount three you are calculating for three so you just do this 3 minus this 3 and we go to what 0 now when you are working in this cell now just go to that column having value 0 having some value 0 and just check out this value this value is 1 so we simply add 1 here so this value is 1 so you simply write here 1 so if you are having coins of denomination 2 & 3 you can make a sum of 3 with one way only and which is that we obviously you can see if you choose one coin of 3 then you can make this 3 so one way is there fine for this one first ways exclude this coin excluded this coin then you have only the then you have only the coin of denomination 2 so we will we will just check your you are calculating for this cell so you just check the upper value 1 you will write 1 plus if you include this coin then what will happen then the rule is what after including this coin just you have to do check this value amount value 4 4 minus this value 3 and we got what 1 so in this same row go to the column having some one here we have 0 the 1 plus 0 is 1 only fine these are simple rules for 5 now how to calculate for this 5 having 0 0 plus 5 minus 3 that is 2 so in this row only go to the column having amount some 2 here we have 1 so 0 plus 1 we are going to tape here 1 only so here what you will write see how about when do we have value one simply if you do not include then just copy the above value 1 then plus if you include this coin then how many ways 6 minus 3 that is 3 so in the same row go to the column having some three here also we have 1 1 plus 1 that is 2 okay now what is there 0 plus 7 minus 3 4 go to the column having for some for 1 1 plus 8 minus 3 is 5 now this row 5 1 plus 1 that is 2 now here 0 plus 9 minus 3 is 6 in this rows will go to the column having some 6 0 plus 2 is 2 here 1 plus 10 minus 3 7 1 1 plus 1 is 2 here 0 plus 11 minus 3 that is we have 8 2 plus 0 that is to 1 plus 2 L minus 3 we have what 9 so 2 plus 1 is 3 0 plus 13 minus 3 is 10 we have to 1 plus 14 minus 3 is 11 this one is 1 plus 2 is 3 here is 0 plus 15 minus 3 is I guess 12 so here we will write 3 plus 0 that is 3 so let us take this this case also now we are going to fill this cell now here we have 5 so this coin value or you can say this row value is greater than this one so we'll write just 0 here also 1 here also 1 here also 1 if you are here we are having fives from 0 to 4 you will write the same value which are in about cell now 4 5 how to calculate simply include simply follow these rules exclude this coin fine now if you are exclude this coin then in how many ways you can make a total of 5 using only the points 2 & 3 the domination of 2 & 3 how many ways are there 1 1 they're only just copy the value of above shall just take the value who goes in plus if you include this coin then how many ways if you include this coin then the funda is simply do five just we are going to calculate for this samne so from that son just minus the value of that denomination 5 minus 5 that is 0 so in the same row you will go to a column having some 0 here we have 1 1 plus 1 is 2 okay now I hope you can fill this table like this so using that method you just fill this table just check out for this one finally see here the amount is 15 and denominations we are having coins of denomination 2 3 5 and 10 now this 15 is you can say this greater than this 10 so will not copy value from our cell if this value is greater than that W value then copy otherwise you have to apply this rule if you do not include this and if you exclude to this 10 then I mean how many ways you can get this total using these coins obviously seven ways just copy the value from above self plus if you include this then how many ways then the method is just do this amount minus the coin coin value 15 minus 10 is 5 and just in the same row go to the column having value 5 so here we have 2 2 that is 9 okay so how many ways are there 9 ways the answer would be always in the intersection of last row and last column so 9 ways are there in 9 number of ways you can make a total of you can make a change of this 15 using these coins now we are going to write the logic for this one see suppose I am taking a 2d array okay where you are going to store the solution suppose this cell is there so I'm taking name of this is a and I and J this cell is a of high value is this one the side the side will we are going to I value I value would be from 0 1 2 3 coins coin says the array 1d array we are taking okay and here we are you taking J this J value from 0 to 0 to 15 we have taken 0 to that amount okay now and thus this area I am going to take name a a 2d array where we are going to store this results the intermediate results fine now you have to apply two for loops what what are those for loops one is for this I and one is within this I within this row I is for row within this row we are going to check the values of columns now so first of all for row then within this row for column for two looks who are going to take first thing what you have to do is simply we are we have just put 1 1 1 here when the amount is 0 so may be simply you can do a off I and column value is this 0 and simply put 0 sorry so I simply put 1 it at all the places and somewhere you find that they they'll start here from 0 denomination 0 then 2 then 3 then 5 and and so if 0 denomination you take then what you will do here only you will take 1 otherwise we 0 0 0 0 0 0 because if you do not have any coin of any denomination obviously then you cannot make the sum you can only make a sum of 0 only ok so now next thing is you have to apply the for loops 1 for loop is for I I is equal to from 0 to hi less than equal to you can say that if you are taking this array name is coins then you can say that coins dot length and I plus then within this loop we are going to take a loop for J for these columns so J is equal to 0 and J is less than equal to this amount even amount amount and J + + now you have to apply the logic have you filled these sales ok simple role is what if if this coin value this row value is less the row value is greater than this amount then simply copy the value from above said fine so just write down just check a condition if points of I is greater than J then what you will do simply pay off I of J is equal to K of I minus 1 and J I minus 1 means from the upper row copy the same value else you will do what else you have to apply the formula that exclude in flu and then add 1 & 2 fine now see else a oh hi J is equal to what we have done else see suppose this one was 5 till 0 to 4 we have copy same value else what we have done this this value plus 5 minus 5 Plus this value from 0 to column 1 plus 1 that is 2 now what you have done is hey oh I minus 1 and J see if I minus 1 is this 1 and J is same row so this value plus plus what we have done hey Oh same row I would be same but we have changed the column column value Hunico out higher column value is this one so column value is this J minus what we have done this 5 minus 5 so J minus see here J value is this one this 5 okay now from 5 we have minus this value J minus points hi because coins is this name of area and I values here too so we have just done five minus five and just taken this value okay and we just add these two venues so this is how the you know main logic is I'm not saying that this is the complete and exact program but this is somewhat the logic you'll write when you will code this thing okay so in next video I am going to discuss with you the second type of coin change problem okay so till then bye bye take care

Channel: Jenny's lectures CS/IT NET&JRF

Views: 166,469

Keywords: dynamic programming, what is dynamic programming, data structures and algorithms, algorithms, coin change problem, ugc net computer science, study material, preparation, GATE computer science classes, coaching classes, best youtube channel for computer science, engineering, cse, IT, CS/IT, b.tech, c programming, notes, pdf, jennys lectures, jayanti khatri lamba, minimum coin change problem, coin exchange, dynamic programming examples, technical, technology, NTA ugc net, syllabus

Id: L27_JpN6Z1Q

Length: 22min 32sec (1352 seconds)

Published: Thu May 23 2019