Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
ฝัง
- เผยแพร่เมื่อ 22 ส.ค. 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!
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!
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.
Where was this guy during my days on campus. Man, I'm impressed. Thank you
haha, hey
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
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/
Thanks for the quality video. You are the most talented algo TH-camr 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
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!!!!
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 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.
Beautiful, why can't my algo teacher be this good 😂
haha yeah
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 TH-cam searches now lol! Great stuff
momma we made it
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 !!
You are a fabulous teacher, crystal clear, thank you so much!
Awesome!
Awesome video! Very well explained. You actually tell the concept of how to solve a dp question rather than just giving the answer.
sure
I needed to watch this video like over and over and over and read about dynamic programming again.
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
I watched many videos on this problem, This one solved all my doubts. Very greatly explained. Thanks a lot!!!
great to hear
I wish I could subscribe again, that's how good this channel is!
thx
@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
Explanation is very clear, thank you very much for providing better than any other paid content for free .
sure - it is what we do.
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/
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!
Understood it for the very first time. Thanks for the repeated and clear explanation. Loved it man.
nice
everyone can be coder , if not they are missing a teacher like u
yes
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
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 😀
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
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
Every video is so clear!
ye
Wow! Your channel is a gold mine.
indeed.
i appreciate your passion, best explanation and grid for ways to make change
Couldn't have explained it better...respect man!
thx
I've looked at a bunch of explanations for how to solve this. Yours is by far the best explanation.
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/
your explanation is really good and easy to understand...this is really helpfull please make more videos like this...
thanks
Thank you so much for explaining this problem ;). I'm new to these tough coding problems. But this video made it so understandable.
sure
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 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
God bless you for this clear explanation I was struggling for hours
Best explanation one can find. Keep it up brother!!!
Thanks
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
Dude, thank you so much for your videos. You are such a natural teacher! : )
sure and thanks.
The audience want to see how did you find the states in bottom up DP. This can we better understand by finding: - Reccurrence relation - Memoization & then Bottom up DP solution.
what
One of the most clear and thoughtful explanations on the subject, thank you for spreading your knowledge, you are an excellent prof!
I love the way you explain stuffs so easily. I was way too confused with this approach before watching this video :) Love ya!!
You are saving my time of solving this problem by myself! Thank you ^^
You should first try by yourself, then you should watch solutions.
I love the video as well as the fact that you always like viewers comment.
yeah lol - I read everything
BEST EXPLANATION EVER!
best explanation to a dp problem i have ever seen.
ye
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
Magnificent explanation!
Sir,keep it up!
ok
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
Great explanation! Thank you...
sure
Your explaining power is very appreciable.Nice video.
hahaha thanks
Awesome, and yeah dont forget to popup tushar roy every once in a while
ye
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.
Love your videos! Very easy to understand! Thank you!
So glad!
How can someone think like this dude, amazing.
im normal
Thanks mate you are the best! Very easy to understand!
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
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
I love the way how he is teaching :D.....thank you
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
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
great video dude...was stuck on this one for the whole day!!
thanks.
This is such a clear explanation...thanks a lot. The best video on coin combinations explanation.👍
sure!
Simply awesome dude ! Keep going ! Really helps having your videos!!
will do
Best teacher superb explanation
thx
You have made these problems soooooo easy to understand!!!
Good Video but a few things missing, to classify a problem as DP we need have the two things first optimal substructure and second overlapping subproblems. You started the video with the solution in terms of DP itself (nice explanation of that ) but it would have been better to approach the problem in a recursive way you know like showing the recursive tree and all, show the repeating subproblems, and then solve the subproblems in DP way(top-down or bottom-up depending on your style). I feel by the way it would have been a better sense of problem-solving. Cause in no way one could tell to solve the problem in DP from like looking at the problem(unless he/she is a pro or solved the problem earlier).
yes
Bravo super clean explanation, one note I think for [] 0 - we can set it as 0 and it will make more sense
thx
Great video and very nice explanation.
thanks
Very Well Explained bruh!!
thanks
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 didn't see any video like your's explaining tabulation in the easiest way .
This guy is just brilliant. Superb job brother
Eh, I'm ok
Sir please make more videos on dynamic programming
Data structures and algorithms
It will help lot of students.
Your videos are very good
ok
Great Video and I like that passionate vibe in your video!!
thx
Wow ! finally someone explained how the tabular method works. Thanks :)
Thank you so much!! Love from India.
Great video :) Just one question - how are we counting 1 when we are using no coins to make the change? Basically, why are we filling the 1st column (for change=0) with '1' for all rows? Shouldn't that be 0 if we think practically?
It means that we want a total change of 0 to be made and it has one unique way and that is to not use any coin that one way is being counted
you make these problems easy to understand!!! thanks for all your efforts :)
sure
Great video man!!! I loved the way you focussed on making everyone understand the subproblem first rather than just filling the table. Btw does Tushar Roy know he is used like a meme here :P?
Thank you, means a lot 🎉 You can also check out our free DSA course - backtobackswe.com/
Man! You rock ❤️, you have exceptional teaching capabilities
thx
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
Best explanation I found about this Coin Change problem, focusing on the subproblem... awesome.! ❤️
Brilliant explanation
thanks
THE BEST explanation I've seen ! Awesome !
This explaination is damn genius! Love it!
we are finding ways to make the change , how can doing nothing make 1 change?
Please let me know if you figure it out.
I forgot the base cases, can you refresh me precisely on the issue. Sometimes base cases do not have an intuitive meaning because of their unusual inputs that don't make sense in the context of normal explanation.
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