Coin Changing Minimum Number of Coins Dynamic programming

Given coins of certain denominations and a total, how many minimum coins would you need to make this total.
github.com/mission-peace/inte...
github.com/mission-peace/inte...

[@MatticusF1nch]

All of your videos are nice and concise. Helping me a lot studying for an algorithms final. Keep 'em up!

[@ericvantassell6809]

Amen to that. Many other youtubers take 20+ minutes on a less effective presentation

[@lanar3528]

You need to explain how you go to the optimal substructure for this problem, that's what I'm struggling with

[@ChaitanyaPaiTechie]

Dynamic programming is now getting easy for me after watching your videos. Thank u for posting.

[@VikasGupta2014]

In DP problems, please start with recursion so that we could understand why it was need of DP here. Anyway awsome tutorial. Thanks a lot.

[@scabbage]

agree

[@jasonng3194]

www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ Here, they have explained why DP is better them recursion. Simply because you can avoid repeated sub problems. But don't look at their DP solution coz it is not for minimum coin change. But the concept is essentially the same.

[@naveenchowdary7959]

he do not kow

[@jk97322]

@Arun Gowda In place of Matrix operation just call the function with same argument can give you a recursion solutions . You can refer geeks for geeks website

[@shashanksagarjha2807]

please check this playlist : kzbin.info/aero/PLeF0b8iqbx4mogykbd82-HY9Y1-JS9MDr

[@AsadShahabuddin]

Really great explanation. Thanks a ton.

[@5k4k1dhtp]

Great video, very concise and understandable.

[@siddharthshah711]

Such a lucid solution! Thanks a lot! :)

[@BorisMediaProds]

I love you, thank you for this tutorial!

[@marcello-6351]

Kudos Tushar! How would you adapt the solution to a real case scenario where coin supply is not infinite? Do you have anything about it? Thanks!

[@atabhatti]

Thanks for making this video. I do have a couple of suggestions for you that will help your audience substantially: 1. Explain why you chose to use dynamic programming vs. recursion vs. some other scheme. 2. Explain why you are doing the min and why each flow of information (either from above or from the left) exists. You explain the mechanics but not the structure of the solution so your video helps me understand how this technique works but does not give me any intuition into where else I might use this solution. 3. Contrast this problem from other similar problems. For example the problem to list the number of ways you can make change from a given denomination of coins for a certain amount. Otherwise, thanks a lot.

[@22PARTHGUPTA18]

+Tushar Roy If you can add separate videos explaining why, they will be of great help and will enable the concepts to get the logic stick. Else these things are very difficult to remember later.

[@YabeDayoo]

chicor2000 smart

[@YabeDayoo]

chicor2000 3 years ago idk

[@YabeDayoo]

IDC

[@ShivangiSingh-wc3gk]

I like this one more than the new one, you speak so fast in the newer version

[@yanlingyang256]

how could you come up with such equation i wonder : )

[@abhishekgupta4360]

All of ur lectures are just awesome.. really great explanation to each of the dp problem.....

[@11m0]

Oh, so this is kindda like the knapsack prob u did...really helpful to know...thx

[@mehulkumarnirala8769]

what if sum =12 in the same example? i am getting segmentation fault

[@anymatix491]

Thanks sir for the solution ,been finding a clearly understandable video for this..

[@borisjurcaga]

Thank you. I solving very similar problem and this video was very helpful.

[@9236261741]

1 5 6 8 should always be in increasing order ? Do I need to sort it before applying in the matrix?

[@marvelfan5444]

Yes, please sort them, so as to build inital rows with step-by-step clarity, as you increase the number of allowed denominations, you understand the pattern that evolves and can get a generalized value for the logic

[@atulmaini1132]

how is the condition if a particular sum cannot be made with current coins in hand?eg if the min value of the coin present is 2 and sum is 3.

[@shubhamgoyal2622]

Until I watched these videos pertaining to the concept of dynamic programming, everything literally went overhead. Now I would safely say I'm getting in the realm of dynamic programming. Thank you.

[@sahildhawan22]

Plain awesome! Just 1 question: Here for 11, I understood until the part where we'll require 2 coins, but couldn't understand the steps that led to determining that the coins were of denomination of 5 and 6.

[@vinzane1412]

Since the last element, 2 (number of coins) has originated from the previous row and the coin[i-1] is 6, it is clear that the solution contains 6 and so traverse back to 6 steps now and you find 1 which has come from it's prev row which is 5, so we also have 5.

[@punitivetoe1819]

How did row for 6 denom val 11 come to 2? Ans. For each cell we want min. Until now min for that denomination is the [i-1][j] val ie that value could have been made by using denominations until i ie 6 excluding 6. Remember each row represents cumulative factor ie considering all coins until i not just i. So using denom 1,5 we can make 11 using 3 coins. Thats the first term of the min i-1,j The question now remains can u make up 11 including 6. If u include 6, remaining value is 11-6 ie 5. So copy the value of min coins using 6 and reaching val 5 which is [i][j-denom ie 6-]

[@ashleycole3054]

awesome video.. keep doing such a great job...

[@VINODKollipara]

great lecture..Thank you for posting it

[@rahilthakkar6007]

thxx man it will save me an hour in examination...its jst amazing! truly grateful to you..

[@no_love_368]

Great work there!

[@sharonbinto]

Thank you so much tushar. Your explanation is really the best and when I tried to code with your explanation. It was very easy and finally when the output came. Really it builds my confidence that I can also code. Thanks for the video

[@qwarlock4126]

You are brilliant.. simply elegantly brilliant

[@CoolDivya1000]

Thanks a lot. It looks quite difficult before your explanation, but your logic is very simple . And please upload a video for Assembly line Scheduling using Dynamic programming. Thanks again.

[@gauravlagad1360]

Very Good Video! I am preparing for Interviews right now, and this is simply the best explanation I have got till now :)

[@alexcui3500]

Do you know how to solve this if negative coin and negative target are allowed?

[@zaktv3595]

do these coins have to be in increasing order? if so i dont see why we would need 2d array since we can simply divide the target by largest coin , then divide remainder by next largest coins and so on. that would give us the min number of coins..

[@rishabh1993able]

awesome......I struggled a lot in this problem now it is clear.......thanks

[@saini85193]

what is logic behind going a[i-1] steps back..?plz explain!

[@morgana_vi]

Because when you have found that it came from coin 6, it means to get 11 you have already included coin with denomination 6, so the remaining is 5 . Now you need to find which coins are included to get 5 for which you need to go to that column, nothing but going 6 steps back.

[@anshumansrivastava8108]

how to check here if the total sum is possible or not using denominations?

[@mymislife]

Helpful! Thank you!!

[@uphaardubey4349]

how can we put in code to see what are actual coins to sum up total??

[@saumya1857]

awsome explanation :)

[@ronakgupta7492]

Hi Tushar by this approach i had to set the first row to Integer.MAX and then was able to run 120 test cases out of 180 in leetcode. I really liked the approch but test cases like [186,419,83,408] sum =6249 giving me 18 instead of 20 idk whats wrong as the code seems to work for every other cases. Please post here if you know where i could be wrong

[@lakshlumba2693]

Hi Tushar , Thanks for the great tutorial. Isn't the else part of this program in github should be like else { temp[i][j] = min ( temp[i][j-coins[i-1]] +1 , temp[i-1][j]) ; } instead of else { temp[i][j] = temp[i][j-coins[i-1]] + temp[i-1][j]; }

[@durgeshmishra1050]

@tushar Roy what if our coins arent in sorted ordder?

[@kiranwali4133]

Thanks a Ton Tushar !!

[@subhashreesahu692]

so quick and understanding easy to grasp

[@dilipdiwakars]

for a coin 5 , why you are saying we have to go back 5 steps back and add 1 to it. Can you please explain. I am not getting that part

[@tejasvigupta07]

How do I fill the first row if I don't have 1 denomination coin? or is this solution requires us to have a coin of denomination of 1?

[@ankitdeshpandey836]

Awesome tutorial

[@123dxakash]

Thanks for the videos. They are very good. One question Whenever the total is not divisible by any of the coins then the algorithm fails. Can you please tell if this issue can be solved?

[@123dxakash]

+Tushar Roy ok thanks for videos anyways one last question How can we find the subset of coins which makes total minimally?

[@deepdesai7859]

u made my exam.. 👍👍this is very help full...

[@Sushil2874]

You explain very nicely..!! Thank you..!!

[@MatteoMircoli]

hi, I don't understand why : for(int i=0; i

[@shrutiawasthi34]

such a nice explanation .. Thanks tushar.. it helped a lot... Keep posting more .:)

[@pragatitanwar1671]

Awesome video!!

[@krishnamali6693]

Hello Tushar, Thanks for helping us all. I tried this algoritham on {2,3,5,7} set of coins with any total weight, it fails. So it is must to have coin of 1 in our set to get correct answer through this algo ?

[@vasanthanv6143]

Hi , Great video , but can you please tell me why are we taking Integer.MAX_VALUE -1 for intialization in the first row and why not Integer.MAX_VALUE ???

[@AyushRaj-pm1dz]

How will the initialization wrok if lets say coins[ ] = {2,4,6} ??? As in this example coins[0] was 1..therefore it worked... Can anyone explain the initilization part..?

[@shelllu6888]

I have watched 4 different types of Money change Dynamic Programming videos, this is so far the best, beating the lecture video from Coursera Algorithm course. If you wanna learn it, watch this first.

[@VaibhavShewale]

well, why do i have different answer then?

[@pranaysanam]

denominations [6,8,9] amount 7 what would be the table values? I mean for eg, take ways at index 7, according to the solution we get 1 but in reality how can you give change to 7 using which 1 coin???

[@davidbarth80]

Lost it at the formula! Anyone can help? Cheers

[@keshavrastogi685]

We have to add one more condition in which we have to check that the row should be greater than 1 , then only we have to check the minimum of both . If we are in the first row , then we have to directly take dp[i][j-a[i]]+1. for(int i=1;i

[@mister_bake2743]

+keshav rastogi Thanks mate, your code is helped me!!!

[@sadmansakib00]

What if we weren't given the coin 1 ?

[@jonathanlong2751]

Thank you so much!.

[@rianchannel9264]

what if the number of coins are limited? can anyone explain me? or give me a link to another video?

[@mrinalmandal914]

Thanks Tushar!!!

[@ShashankGupta_Shanki]

great explanation...:)

[@how2tech403]

can you explain intuition behind the solution??

[@jg8742]

dear sir . it would be helpful If you explain the problem with code also. As it is very difficult to code, although conceptually it is easy I was looking for an explaination like your trees playlist

[@glennpavel4800]

hi, idk if I understand wrong from 1 or position 6 value 5 , five positions back is 0 , like this 1-1 pos =4, -1 pos = 3 ... -5 = 0 not 1 has you show in minute 3:20 , or I'm doing something bad? thanks for your help

[@yudiguzman8926]

Great. Thank so much.

[@yanivgardi9028]

thanks Tushar. This post is very helpful.

[@mohammedsafwan4447]

thanks bro very helpful :)

[@hankesteveo]

I kept up for a minute. Very good.

[@gunjanbarhaiya297]

Sir the trick you give to deal with dynamic programming is superb! But i just wanna know how can i develop the logic or trick as you do?

[@aditya234567]

practice!

[@velramesh05]

Good explanation sir, thank you.

[@DeepakSharma-di2fd]

simply awesome

[@DarlingMySweet]

I think of it like this: Say we want to put [2, 5, 3] into 7, and we've already figured out that there is 1 way to put [2, 5] into 7. To add 3 to the mix we just add the number of ways that [2, 5, 3] goes into 4. The logic is that since 7 - 3 = 4, any combos that have 3 in them will be with some coin mix that totals 4. So [2, 5] into 7 = 1 + [2, 5, 3] into 4 = 1, means that [2, 5, 3] into 7 = 2.

[@shivjeetsingh8666]

Nice video lecture. please upload more concept of dynamic programming.I solved many problem of Hacker Rank. Thanku :)

[@weixing8985]

Thank you!

[@johnhammer8668]

3:16 why go back coin value steps back? Why does this work?

[@sheenamjindal6703]

wondering if it really solves the problem by writing the core logic you provided in the video. I tried but it didnt work for me,

[@hamicartoon]

Can't we solve this using window replacing

[@XAngelsLifeX]

Спасибо за видео

[@mingleizha8868]

It is knapsack problem except you are trying to get the number of items!

[@aziz9488]

True, it's the same as the unbounded knapsack problem

[@05.nguyenkhanhduy9]

i can asking you if not changing = total how to code ?

[@jesanahammedovi9061]

If we don't have $1 bill then what happen in 1st row?

[@sanjeevshukla3821]

i think we need a 0th row containing all 0's. so that if coin denomination starts from a number which is greater then the sum. then copy old value from top.

[@fahadmohdshahid4110]

We need to fill it by infinite(int_max) not by 0.

[@harikrishna6233]

Thanks a lot .. its very helpful

[@yernartalgatuly4252]

what is the difference between this problem and subset sum problem?

[@yernartalgatuly4252]

***** Understood. Thanks

[@stith_pragya]

superb explanation and Thank You Tushar Sir....

[@SUDHIRKUMAR-vh9pd]

hi Tushar...nice video.... what happens if there is no coin having value 1 ; ex total sum =10 coin ={3}

[@islamtaison8051]

عالنعمة انت شبح .. تسلم ^_^

[@md.razaulhaquesubho4710]

how can you solve this problem for {2,4,6} to make 8 ??

[@123dxakash]

+Shuvo Opu just use the condition if(i==0) { if(j%coins[i]==0){ t[i][j]=j/coins[i];} else t[i][j]=0; }

[@joyshah_22]

Excellent explaination💯💯💯

[@ihashib]

Traced your code with the matrix you made, have a little problem, at min{T[i-1][j], 1+ T[i][j-coin[i]}, gonna consider that the 2d matrix has 0 as dummy index, so min{0, 1+ (0-1)}, so min will select, 0. So, T[1][1] is 0 not 1. If i don't consider 0 as dummy index, then it'll give error. Confused.

[@sainathtallam9262]

great tutorial

[@prinzmukka]

Good one !!

[@routhukishore7643]

how it works in case of 2, 5, 6, 8 and total = 11 ?

[@marouane55]

you cant have 2,5,6,8 cents without 1 cent it is the base (2 cents doesn't make sense without 1)

[@rabindrapatra7151]

@@marouane55 if something is not working then we need to made assumption or base case.

[@esmamouine2422]

trop bien mr.tushar.

[@rajamalakar7576]

is it not necessary to sort the coins in asc .. please answer..

[@wpavada3247]

No it is not necessary

[@HarishAmarnath]

yes it is necessary to sort, in dynamic programming way, we need to know the result of 1 to find the result of 5 hence it should be sorted first

[@riyankpatel9410]

Great sir🙏

[@hackerexpert6819]

what if there is no coin of denomination 1

[@karansaxena4422]

ide.geeksforgeeks.org/VivacD

[@morgana_vi]

this gives a wrong answer then. I think that is why he made another video

[@pratikgupta3089]

then give a very large value to those cells where V