Coin Changing Minimum Number of Coins Dynamic programming

[@sharanbalajimanickamoorthy3639]

The best video on this topic and this example. I understand DP much better after this video. Thank you so much!

[@ChaitanyaPaiTechie]

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

[@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

[@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.

[@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

[@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

[@lanar3528]

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

[@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.

[@rahilthakkar6007]

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

[@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.

[@qwarlock4126]

You are brilliant.. simply elegantly brilliant

[@AsadShahabuddin]

Really great explanation. Thanks a ton.

[@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!!!

[@stith_pragya]

superb explanation and Thank You Tushar Sir....

[@swadheenta.957VBTS]

Nice explanation solved my doubt thank you 💜

[@rishabh1993able]

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

[@subhashreesahu692]

so quick and understanding easy to grasp

[@11m0]

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

[@pre_ty_things]

I am not sure if we really need 2D Dp. I did in one memo[0] = 0; for (int i = 1; i = coins[j]) { memo[i] = Math.min(memo[i], 1 + memo[i-coins[j]]); } } } return memo[amount];

[@ShivangiSingh-wc3gk]

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

[@abhishekgupta4360]

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

[@cristianouzumaki2455]

More appropriate title would say " infinite denominations of same coin available"

[@joyshah_22]

Excellent explaination💯💯💯

[@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

[@siddharthshah711]

Such a lucid solution! Thanks a lot! :)

[@anymatix491]

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

[@my3m]

So much better explained than AlgoExpert

[@qandrea1015]

If 1 it is not in the coins. Just initialize T properly: in the first row of T we put +inf if j < "the smallest coin" (coin[1] in my case, I added zero in coin[0]). And then we fill the fist row with T[0][j] = T[0][j-coins[1]]+1 coins.sort() for i in range(len(coins)): T.append([]) for j in range(amount+1): T[i].append(0) for j in range(1,amount+1): if j < coins[1]: T[0][j] = float("inf") T[0][0] = 0 for j in range(1,amount+1): if coins[1]

[@BorisMediaProds]

I love you, thank you for this tutorial!

[@gauravlagad1360]

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

[@5k4k1dhtp]

Great video, very concise and understandable.

[@Sushil2874]

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

[@subodhjain8249]

code for the lecture m=size of array n=sum :) int count( int S[], int m, int n ) { // table[i] will be storing the number of solutions for // value i. We need n+1 rows as the table is consturcted // in bottom up manner using the base case (n = 0) int table[n+1]; // Initialize all table values as 0 memset(table, 0, sizeof(table)); // Base case (If given value is 0) table[0] = 1; // Pick all coins one by one and update the table[] values // after the index greater than or equal to the value of the // picked coin for(int i=0; i

[@ashleycole3054]

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

[@shrutiawasthi34]

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

[@raghibmusarrat1471]

You algorithm gives wrong answer for the following problem: COINS: 2,3,5 Sum: 7 Please tell how to tackle this. The answer it gives is 0

[@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

[@pragatitanwar1671]

Awesome video!!

[@yanivgardi9028]

thanks Tushar. This post is very helpful.

[@no_love_368]

Great work there!

[@velramesh05]

Good explanation sir, thank you.

[@borisjurcaga]

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

[@mohammedsafwan4447]

thanks bro very helpful :)

[@VINODKollipara]

great lecture..Thank you for posting it

[@deepdesai7859]

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

[@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.

[@dongyuchen8625]

if there isn't $1 coin this wouldn't work right?

[@DhirajKumar-jf1yu]

If you implement the same way what he explained, it won't work if there isn't $1, but he has implemented in different way in his GitHub link. Even I implemented my code same way he explained and it fails if it doesn't have $1.

[@dongyuchen8625]

@@DhirajKumar-jf1yu Thanks mate. I solved it by set the initial values in the table to [0,'inf','inf'...'inf'], only update the value when the index is bigger than the coin. When the coins can't match the total value the last element in the table would always be 'inf'. But Tushar's video do give us a great example.

[@sadmansakib00]

What if we weren't given the coin 1 ?

[@harikrishna6233]

Thanks a lot .. its very helpful

[@sainathtallam9262]

great tutorial

[@kittyjain4682]

@Tushar Roy - You just started with the solution without explaining why ? It's not going to help anyone if we have to memorize it without knowing y.

[@rushabhshah434]

There is an error in 2-3rd line it should be min( T(i-1)(j)+1,T(i)(j-coin(i) ) Here logic is ...let me explain by example of the 6 in above table..now filling matrics we've 2 possiblity to get desired value either 6 is included or not if 6 is not included then we copy above's i.e. here 5's answer for that value of i If 6 is included then we've to add other coins accordingly for obtainig the desired value.Now,we check wether this ans. With 6 is optimal or not by checking it with above ans. I.e. here 5's ans. Which is already optimal uptill that 5 for j Ty !

[@kiranwali4133]

Thanks a Ton Tushar !!

[@shivjeetsingh8666]

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

[@ankitdeshpandey836]

Awesome tutorial

[@riyankpatel9410]

Great sir🙏

[@BRBallin1]

What about examples where 1 isn't a coin denomination? Then there is no "top" value to use

[@user-rqyjdhueklaq]

sum = 14 number of coins 3 2 3 5 Your algorithm gives wrong solution

[@youssifkhairy1725]

You should Sort Numbers First

[@Kasa99]

no need to sort

[@henryhardcore8584]

This algorithm doesn't check if the sum is possible to add up. If we have coins 2, and sum = 10.

[@saumya1857]

awsome explanation :)

[@chandan_prabhakar]

nice video gautam gambhir

[@esmamouine2422]

trop bien mr.tushar.

[@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.

[@shobhitranjan3957]

The solution won't work if no denominations are possible.

[@ShashankGupta_Shanki]

great explanation...:)

[@boosan_m]

Am I missing something? 1. This solution seems to work only for coins with 1 in it [2,3,5] & 11 won't work 2. Github link has a different solution in it.

[@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.

[@hankesteveo]

I kept up for a minute. Very good.

[@DeepakSharma-di2fd]

simply awesome

[@anshumansrivastava8108]

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

[@nishanksoni7120]

You never explained why this logic is working. And why we are going for DP and what dp approach we are using

[@mymislife]

Helpful! Thank you!!

[@arunabhhejib1136]

Every time I see your video I get the solution but have no idea how to get there. It would be better if you start from recursion and then lead to finding an optimal substructure and so on.

[@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

[@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.

[@parthhingu1525]

excellent teaching😊

[@ivandrofly]

Finds min number of coin you will give as a change for example

[@manojpandey7517]

He says "yes we will use dynamic programming..." and directly jumps to fill the table out of nowhere. That's why I could never learn anything from him. A bad technique to teach DP. The first and foremost step must be finding the recursive solution. I don't know why a lot of people out there recommend Tushar's video. I tried to watch his videos with a fresh mind but every time I felt let down. Sorry, but I cannot say "awesome tutorial" if I didn't learn anything. This is the last attempt I'm here.

[@tricktreat7941]

His videos are not for people like you. Tushar is the smartest LeetCoder on KZbin. You need to reach a certain level before you can make use of his contents. When you do, you will realize why people recommend him.

[@manojpandey7517]

@@tricktreat7941 it isn't about being smartest. He's teaching and a teacher doesn't need to be smartest to teach well. All I'm saying that this isn't a good way of teaching dynamic programming. If you want to know what a better way can be, watch Aditya Verma's dp Playlist.

[@manojpandey7517]

Another user has also pointed out and suggested him to first explain what's tempting him to use dp.

[@ucanhly1166]

I think the best teacher of algorithm on yt is Abdul Bari but actually haven't a lot of videos of dp but I learn from him so much and I came here to understand how to fill the table =))

[@yudiguzman8926]

Great. Thank so much.

[@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 ???

[@omarosmanov727]

How to actually print out all combinations of amount? Let us say for amount=4, coins=[1,2,3] need to print out: (1,1,1,1); (2,2); (1,1,2);(1,3)

[@TheNayanava]

that should be fairly easy. just run a dfs. create a List> as your result. add the coin to the list and subtract that amount from the list before calling dfs recursively. once you hit 0, you can append that list to your result. Don't forget to do a res.add(new ArrayList(list)). else it will keep pointing to the same list. Now while backtracking you can remove that coin from the list and try adding a new coin as long as the value of the coin is not greater than the amount. Please see this solution will actually have O(n^n) time complexity.

[@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,

[@yanlingyang256]

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

[@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

[@MayankSingh_is_me]

for coins = [10, 50, 100, 200, 500, 1000] and total = 11, noobs wud get stucked. having coin of denomination "1" in the very beginning takes away some critical aspect making everything a happy case! @TusharRoy: can u comment?

[@HarshaVardhan-kq1sv]

Excellent sir. I have a doubt sir if we have multiple solution then how sir. Ex - coins: 1 2 3 Total: 4 Then dp tables will be 0 1 2 3 4 1 0 1 2 3 4 2 0 1 1 2 2 3 0 1 1 1 2 As dp[3][4] is 2, where the 2 is coming from above one as well as the 2 is coming from dp[3][1] i.e (1,3) and (2,2) So how we can traverse as we have multiple solutions like this. Sir can you explain this please sir.

[@rahuldevgupta4513]

It feels as if I am cramming the solution

[@allanmagalhaes8211]

lol i guess i understood everything until the final minute when you ran coding with no pauses

[@johnhammer8668]

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

[@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 ?

[@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-]

[@MiguelCarvajalIB14]

You got column and rows reversed, it is a bit confusing...

[@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

[@mohammad-sm3zt]

thanks a lot Tushar

[@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!

[@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

[@diegogusava]

Thanks Tushar!!!

[@divyaanshu7387]

In first column you wrote 0.But in the another example you used 1.What is correct way.And that should be 1 beaoz there is possibility not to give change.

[@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!

[@pbdagr]

U r awesome in problem solving

[@prinzmukka]

Good one !!