Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
VloĆŸit
- Äas pĆidĂĄn 20. 08. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
đč Intuitive Video Explanations
đ Run Code As You Learn
đŸ Save Progress
âNew Unseen Questions
đ Get All Solutions
Question: You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have an infinite number of each kind of coin.
Examples:
1
Input: amount = 5, coins = [1, 2, 5]
Output: 4
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
2
Input: amount = 3, coins = [2]
Output: 0
Can't make change for this amount given the coins we have.
This problem is very similar to the 0 / 1 knapsack problem.
We will use a bottom up dynamic programming approach to build to our final answer.
We will consider the total ways to make change with just the 1st coin, with just the 1st and 2nd coin, with just the 1st, 2nd, and 3rd, coin, and so on...
Complexities
A is the amount to make change for.
n is the total denominations avaliable to us.
Time: O( A * n )
For each denomination we will be solving A subproblems. So for each of the n we will be doing A work, hence multiplication.
Space: O( A * n )
Hold the answer to all subproblems.
Note: We can do this in just O( A ) space but we did it this way for simplicity
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Table of Contents:
Addressing Temporal Circumstances 0:00 - 0:11
The Problem Introduction 0:11 - 1:30
Outlining Our Subproblems 1:30 - 2:50
Defining Our Base Cases 2:50 - 3:45
Establishing Our Subproblem Relationship 3:45 - 4:31
We Are Ready: Filling Out The DP Table 4:31 - 10:28
Time Complexity 10:28 - 10:40
Space Complexity 10:40 - 11:10
Wrap Up 11:10 - 11:23
The code for this problem is in the description. Fully commented for teaching purposes.
Couldn't find link to the code for this problem in the description ... Awesome Explanation by the way !!!
thx and we only maintain backtobackswe.com now
bro, briliant thx, but, I could not get one thing which is not explained to any videos I've searched for:
What if the amount of change would be 6 in your case. wouldn't it fail? or am i missing something.
for example just consider and explain to me this please:
in case the chaneg is 6 for the cell {coins[1, 2] x change[6] } = we would have 1 + 3 = 4. (6-2=4 and on 4th collumn in current row we already have value 3 (ways) ).. that means that for change 6 if we use coins [1,2] we have 4 distinct was?! but thats not true.
we have only 1+1+1+1+1+1; 2+2+2; 2+2+1+1; and the final one 2+1+1+1+1 is to be honest is same way as 2+2+1+1. e.g. aren't all cases all instances of (2 * n +1 * m) = C (c = any positive change value) all same ONE distinct way of forming change for that C?(where n, m are positive integers >0) ? thank you anyway!
e.g For change 6 there should be 3 distinct wasy: 1) using coin 1 only, 2) using coins 1 & 2 any number of times 3) Using only coin 2?
in other words, using coin1 two times and forming a change and using coin1 4 times and forming a change with same coin2 one time or two times, isn't it same unique way by using coin denominations any arbitrary times?
"Every single dynamic programming video should start out with the explanation of the subproblem.
This is not about table behind me. Itâs about subproblem and how they relate to each other."
Love this!
I love the way you merged your video with that of Tushar roy's. đ
Yeah, I mess around sometimes. I've seen all the gurus.
@@BackToBackSWE you gonna become one of the gurus , then hopefully the ones watching your videos :)
@@ravitanwar9537 haha
but I really hate the fake accent of tushar but he also have nice explaination
@@shrad6611 he gives no explanation at all
Iâve lost it when I saw Tushar đ Great work man!
my bad, old me was annoying
@@BackToBackSWE What? Noo, it was hilarious :D I love it when I see this kind of references :D
@@ilventoro nice
đ€Łđ€Łđ€Łđ€Łđ€Łđ€Łđ€Łđ€Łđ€Ł
Same here đ
Amazing work! You explain things in a way that even a 6 yrs old child can understand. Keep it up!!
haha thx
yeah definitely!
Knowing a concept is one thing, but being able to explain it so well is another .Your explanations are lucid and very easy to understad.
Bro, my friend asked me to explain this problem even though I knew solution I messed up because explaining DP approach to someone else sucks, but your explanation is brilliant.
nice, thanks
I love how you explain this problem and the use of the disclaimer "do not memorize the patter, memorize the subproblem". Your order of explanation, repetition, knowledge of the subject, the thoroughness of your explanation and your enthusiasm are amazing! Thank you for creating this!
You're very welcome!
Great Explanation! Just loved when you described that a DP problem is not about just showing a dry run.
Just some additions, to be precise the subproblems are -
#ways to get a sum 'n' using S(a,b,c) set of coin = # ways of getting a sum 'n' from S (a,b) (Do not use the c coin) + #ways of getting a sum 'n' from S(a,b,c) with using c at least once (Use the c coin).
This is true as basic set law {X union X complement is equal to universal set} therefore, doesn't matter which coin is choosen as c, therefore it doesn't matter that the order of coins is in ascending order or not.
Now, how to ensure taking at least one coin c => use one coin of c and find #ways of getting a sum of n-c from S(a,b,c) {i.e., for getting sum n-c, it doesn't matter whether coin c was taken or not}
thx and thx
Where was this guy during my days on campus. Man, I'm impressed. Thank you
haha, hey
I have recommended all of my friends who wanted to learn dp this channel.....His shear passion and excitement to teach itself crystal clears all the concepts and doubts...and of course he taught me to think about subproblems...Thank you for this wonderful explanation!!!!
Really love how concise and informative this video is! Instead of getting straight into coding, thank you for drawing out the table and helping us reason through it in a way that actually makes sense and is succinct!
Happy Holidays! Really glad to help đ Do you know about the 5 Day Free Mini Course? Check it out here - backtobackswe.com/
Bro, I'm from Toronto. THIS RIGHT HERE IS THE BEST EXPLANATION. Most folks must just go into the table. You did everything. Thank you
Thanks for the quality video. You are the most talented algo CZcamsr out there!
Note to viewers: If we call this the âunlimitedâ 0/1 knapsack problem (you can choose unlimited numbers of elements) and the other video Ben refers to as the âbasicâ 0/1 knapsack problem(you can only choose each element at most once) , the only difference between the two seems to be which cells we check with when we fill the table. For both the âbasicâ and âunlimitedâ problem, we will check the cell right above the current cell to assess the case when we donât choose the current element. However, when we choose an element, the âbasicâ knapsack checks the element that is one row above and element number to the left whereas for the âunlimitedâ case we just look at the cell in the same row and element number to the left. I think this is a useful perspective to store somewhere in the back of oneâs head.
thanks null
Thanks man, great job. Your explanation is top class. Not many people who know these problems can explain in such a manner.
Thank you. It is my mission to make things as clear as possible.
Honestly what's college without you, my school needs you! Thanks for all the great information and bringing it all together. I am adding "back to back swe" to each of my CZcams searches now lol! Great stuff
momma we made it
Beautiful, why can't my algo teacher be this good đ
haha yeah
Awesome video! Very well explained. You actually tell the concept of how to solve a dp question rather than just giving the answer.
sure
This is why I love youtube, a person overseas just helped me understand a very crucial technique of dp .. Thank You sir, Keep making such awesome videos!
I watched many videos on this problem, This one solved all my doubts. Very greatly explained. Thanks a lot!!!
great to hear
For folks who still don't understand the intuition behind "table[row][col - coins[row-1]" and "table[row-1][col]"
Amount 5, with coins [1,2].
There are 3 ways:
[1+1+1+1+1]
[1+1+1+2]
[2+2+1]
Can be broken down as:
With 2:
Deduct 2 from amount 5, then you have. sub problem which is:
Amount 3, with coins [1,2]
[1+1+1] = 3. Now just add 2 to it ==> [1+1+1+2] = 5
[2+1] = 3. Now just add 2 to it ==> [2+1+2] = 5
Without 2:
[1+1+1+1+1]
thanks
Thank you saved my night ! I was trying to understand the logic behind this since long time !!
@BackToBackSWE Ben, I enjoy watching your videos more than watching Netflix TV shows man! You help understand the problem so well that I can easily codify it. No need to remember solutions, only patterns!!
ye
Really well put. I had no prior experience in dynamic programming and after watching this I was able to solve most of the partitions problem that I encountered. Thank you.
Nice! Happy for you
You are a fabulous teacher, crystal clear, thank you so much!
Awesome!
Understood it for the very first time. Thanks for the repeated and clear explanation. Loved it man.
nice
This is much better than Tushar's video in terms of explanation, I think the explanation of using and not using the coin in the list on each step makes way more sense
thanks
Damn i just started dynamic programming and i am so grateful i came across your videos! you just explained so flawlessly! Keep up the great work man!
thx
Explanation is very clear, thank you very much for providing better than any other paid content for free .
sure - it is what we do.
I needed to watch this video like over and over and over and read about dynamic programming again.
everyone can be coder , if not they are missing a teacher like u
yes
I wish I could subscribe again, that's how good this channel is!
thx
I've looked at a bunch of explanations for how to solve this. Yours is by far the best explanation.
One of the most clear and thoughtful explanations on the subject, thank you for spreading your knowledge, you are an excellent prof!
Thank you so much for explaining this problem ;). I'm new to these tough coding problems. But this video made it so understandable.
sure
I watched a lot of videos on knapsack and coin problem but i t hink this is the first time i actually finally understood that damn table - thank you :)
sure
This is second video after o/1 knapsack i've watched of this guy. I really appreciate ur work. U are making it easy for beginners in dp like me to understand the logic as well as recurrence relation which is very important in dp. Thank you again for great explanation. I hope u make more and more videos on dp and other competitive programming topics.
Hey, this guy here. Thanks for coming by
thx bro! you've helped me a lot! I was struggling to understand this problem quite a long time. Goood work!
Awesome! Try our 5 day free mini course for some great content backtobackswe.com/
Understood that if amount is 0, only one way to select coins i.e. choose nothing. On the other hand, if number of coins to choose is 0, there's no way to choose any coins, hence 0.
However, in an overlapping case of if the amount is 0 and there are no coins to choose, why it's one way (value for table[0][0])
By the way, recently started following your videos. love your unique style of presentation on difficult topics. Feels like reading a well written documentation :D
It is hard to justify, it just makes the recursion "work". We could conceptualize a justification if we wanted to and that'd be fine. and thx
Wow! Your channel is a gold mine.
indeed.
Every single dynamic programming video should write out the underlying recurrence relation
Sure, try out our 5 day free mini course for some cool stuff backtobackswe.com/
Very clear explanation what the table actually means. Very much needed as a self taught software engineer! Thank you
You are welcome. I want to thank you for even giving me your attention because that matters to me. So thank you, I wish you success.
your explanation is really good and easy to understand...this is really helpfull please make more videos like this...
thanks
You sounds like my Zoology teacher. He told us that "If I repeate a line many times, it will hit you minimum once". That's might be the reason for what I was able to understand what he was saying at the very last second of explanation. Take love â€
nice
I love the way you explain stuffs so easily. I was way too confused with this approach before watching this video :) Love ya!!
Couldn't have explained it better...respect man!
thx
Dude, thank you so much for your videos. You are such a natural teacher! : )
sure and thanks.
i appreciate your passion, best explanation and grid for ways to make change
Your explaining power is very appreciable.Nice video.
hahaha thanks
I love you ! I love your explaining ! crystle clear!
thanks
THIS IS THE BEST DP PROBLEM EXPLANATION EVER. THANKS!
Thank you, glad you liked it đ
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends đ
I finally could understand how to solve this problem that I had seen in SICP book. Thank you guys
Happy Holidays đ Thank you for your kind words, Luis! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
God bless you for this clear explanation I was struggling for hours
Got the algo concept in ur video after failed attempts in understanding the same in two different videos.That said, u r clearer to me
one of the best explanation videos. Clear as always, thank you
thanks
Great explanation! Thank you...
sure
Every video is so clear!
ye
Best explanation one can find. Keep it up brother!!!
Thanks
How can someone think like this dude, amazing.
im normal
It's amazing how you understand algorithms in this much depth, while still doing undergrad in school!!!
I got a master's degree and 4 yoe, still learning algorithms from you. Thank you for sharing, and keep the good videos going!
Haha sure
best explanation to a dp problem i have ever seen.
ye
Magnificent explanation!
Sir,keep it up!
ok
I love the video as well as the fact that you always like viewers comment.
yeah lol - I read everything
holy shit, I just learning dynamic programing and searching how to make dp table. this video is so easy to understanding. thanks a lot!!
sure
This is such a clear explanation...thanks a lot. The best video on coin combinations explanation.đ
sure!
This guy is just brilliant. Superb job brother
Eh, I'm ok
Awesome, and yeah dont forget to popup tushar roy every once in a while
ye
Best explanation I found about this Coin Change problem, focusing on the subproblem... awesome.! â€ïž
One comment that I was using the algorithm on the Hackerrank preparation kit, each coin in the array must be less or equal to the target amount. Otherwise, the algorithm breaks. Thank you for the clear explaination.
I love the way how he is teaching :D.....thank you
haha ive watched your coin change problems probably like 10x now. Idk i keep forgetting the method behind the madness. Thank you so much for making these videos though :) As a non commsci major, I''m super grateful you're making these videos! -headed into my google phone screen tmr
Thanks for putting out awesome videos! I think it would more informative on DP questions if you went through and developed the recursive formula before diving into the table. The explanation is on point but there was no explanation why we would use DP in the first place. For someone who had never seen the problem before, they wouldn't be able to instantly identify it as DP and determine the table structure and what the sub problems are. I think approaching the problem and determining why DP is necessary would be helpful.
I made a page dedicated to things like this: backtobackswe.com/im-sorry
@@BackToBackSWE I agree with Patrick Lown, maybe explain how to come up with DP programming for solving this problem. Really like your amazing video
@@kellyxiao3060 thanks
God bless this man for his videos
I almost punched my monitor for this problem, but then i remember back to back swe is there to save my day and calm my adhd when solving problems
hahahahaha - that's why u need a 2nd monitor :0
Wow ! finally someone explained how the tabular method works. Thanks :)
I struggle to understand iterative approaches towards dp problems. your video was great help! thanks ben!
Awesome video! I think a follow up that would be cool is to optimize this problem with the O(A) space complexity and maybe explain how and why we can optimize it the way we can sort of continuing on from here! Thanks for the vids! Keep up the good work!
thanks
doing a great job man!
just one suggestion : it would be nice if you make playlists and group similar concept questions together!
thanks and ok
You are saving my time of solving this problem by myself! Thank you ^^
You should first try by yourself, then you should watch solutions.
Thank you so much!! Love from India.
I didn't see any video like your's explaining tabulation in the easiest way .
Best teacher superb explanation
thx
BEST EXPLANATION EVER!
Man! You rock â€ïž, you have exceptional teaching capabilities
thx
great video dude...was stuck on this one for the whole day!!
thanks.
Great job mate, your pedagogy is extremely articulate and thorough compared to the vast majority of videoes online.
**googles pedagogy** Thanks ha
Bravo super clean explanation, one note I think for [] 0 - we can set it as 0 and it will make more sense
thx
Sir please make more videos on dynamic programming
Data structures and algorithms
It will help lot of students.
Your videos are very good
ok
thank you for making me understand this :)
sure
THE BEST explanation I've seen ! Awesome !
Love your videos! Very easy to understand! Thank you!
So glad!
you make these problems easy to understand!!! thanks for all your efforts :)
sure
Thanks mate you are the best! Very easy to understand!
I pause the video at 4:23 and think for a moment which helps me to understand the solution better.
Really great explanation. Thanks for making this. I wish we can see how we go from Recursion to Top Down to Bottom up approach like this..That would help a lot and getting intuition behind this problems.
Sure, and got it
Simply awesome dude ! Keep going ! Really helps having your videos!!
will do
Great video and very nice explanation.
thanks
I especially like your table notation which is self explanatory
thanks
Thank you so much for explaining this helps a lot
All folks do subscribe to his channel and hit like :)
sure
ye
Brilliant explanation
thanks
Great Video and I like that passionate vibe in your video!!
thx