Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
Вставка
- Опубліковано 18 вер 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!
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
Thanks for the quality video. You are the most talented algo UA-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
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.
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/
Where was this guy during my days on campus. Man, I'm impressed. Thank you
haha, hey
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
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
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
You are a fabulous teacher, crystal clear, thank you so much!
Awesome!
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 UA-cam searches now lol! Great stuff
momma we made it
Awesome video! Very well explained. You actually tell the concept of how to solve a dp question rather than just giving the answer.
sure
@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
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 !!
I wish I could subscribe again, that's how good this channel is!
thx
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
I needed to watch this video like over and over and over and read about dynamic programming again.
your explanation is really good and easy to understand...this is really helpfull please make more videos like this...
thanks
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!
Thank you so much for explaining this problem ;). I'm new to these tough coding problems. But this video made it so understandable.
sure
Understood it for the very first time. Thanks for the repeated and clear explanation. Loved it man.
nice
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 love you ! I love your explaining ! crystle clear!
thanks
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/
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
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.
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
Great explanation! Thank you...
sure
Your explaining power is very appreciable.Nice video.
hahaha thanks
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
I've looked at a bunch of explanations for how to solve this. Yours is by far the best explanation.
Couldn't have explained it better...respect man!
thx
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
Every video is so clear!
ye
one of the best explanation videos. Clear as always, thank you
thanks
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
God bless you for this clear explanation I was struggling for hours
everyone can be coder , if not they are missing a teacher like u
yes
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.
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
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
Best explanation one can find. Keep it up brother!!!
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 😀
Magnificent explanation!
Sir,keep it up!
ok
One of the most clear and thoughtful explanations on the subject, thank you for spreading your knowledge, you are an excellent prof!
best explanation to a dp problem i have ever seen.
ye
How can someone think like this dude, amazing.
im normal
This is such a clear explanation...thanks a lot. The best video on coin combinations explanation.👍
sure!
Awesome, and yeah dont forget to popup tushar roy every once in a while
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
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
I love the way you explain stuffs so easily. I was way too confused with this approach before watching this video :) Love ya!!
Love your videos! Very easy to understand! Thank you!
So glad!
Best teacher superb explanation
thx
great video dude...was stuck on this one for the whole day!!
thanks.
This guy is just brilliant. Superb job brother
Eh, I'm ok
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/
I struggle to understand iterative approaches towards dp problems. your video was great help! thanks ben!
Bravo super clean explanation, one note I think for [] 0 - we can set it as 0 and it will make more sense
thx
You are saving my time of solving this problem by myself! Thank you ^^
You should first try by yourself, then you should watch solutions.
Man! You rock ❤️, you have exceptional teaching capabilities
thx
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.
Thanks mate you are the best! Very easy to understand!
Simply awesome dude ! Keep going ! Really helps having your videos!!
will do
you make these problems easy to understand!!! thanks for all your efforts :)
sure
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
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
God bless this man for his videos
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
thank you for making me understand this :)
sure
Best explanation I found about this Coin Change problem, focusing on the subproblem... awesome.! ❤️
Awesome explanation... I just like the way you present the problem thinking approach 👍💯
thx
amazing how well you teach!! Thanks for great work you do!
I love the video as well as the fact that you always like viewers comment.
yeah lol - I read everything
THE BEST explanation I've seen ! Awesome !
Great video and very nice explanation.
thanks
Sir please make more videos on dynamic programming
Data structures and algorithms
It will help lot of students.
Your videos are very good
ok
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
Great Video and I like that passionate vibe in your video!!
thx
Thanks a lot for your videos Ben! I can see the subproblems in many DPs now!
BEST EXPLANATION EVER!
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
I love the way how he is teaching :D.....thank you
amazing explanation..thanks for this video :)
thanks and sure
Best explanation. Clear, concise. Thanks 👍
You have made these problems soooooo easy to understand!!!
I didn't see any video like your's explaining tabulation in the easiest way .
You are great bro !!!
Thank you for lesson. 👏👏👍👍👍
sure
I especially like your table notation which is self explanatory
thanks