Total Unique Ways To Make Change - Dynamic Programming ("Coin Change 2" on LeetCode)
HTML-код
- Опубликовано: 19 янв 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 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 😁
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!!!!
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!
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 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.
Thanks for the quality video. You are the most talented algo RUclipsr 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
Where was this guy during my days on campus. Man, I'm impressed. Thank you
haha, hey
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 RUclips searches now lol! Great stuff
momma we made it
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
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
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, I'm from Toronto. THIS RIGHT HERE IS THE BEST EXPLANATION. Most folks must just go into the table. You did everything. Thank you
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
Awesome video! Very well explained. You actually tell the concept of how to solve a dp question rather than just giving the answer.
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
I love the way you explain stuffs so easily. I was way too confused with this approach before watching this video :) Love ya!!
Understood it for the very first time. Thanks for the repeated and clear explanation. Loved it man.
nice
Beautiful, why can't my algo teacher be this good 😂
haha yeah
I watched many videos on this problem, This one solved all my doubts. Very greatly explained. Thanks a lot!!!
great to hear
One of the most clear and thoughtful explanations on the subject, thank you for spreading your knowledge, you are an excellent prof!
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!
Thanks a lot for your videos Ben! I can see the subproblems in many DPs now!
Dude, thank you so much for your videos. You are such a natural teacher! : )
sure and 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/
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 needed to watch this video like over and over and over and read about dynamic programming again.
Simply awesome dude ! Keep going ! Really helps having your videos!!
will do
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
great video dude...was stuck on this one for the whole day!!
thanks.
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
Wow! Your channel is a gold mine.
indeed.
Your explaining power is very appreciable.Nice video.
hahaha thanks
amazing how well you teach!! Thanks for great work you do!
Explanation is very clear, thank you very much for providing better than any other paid content for free .
sure - it is what we do.
you make these problems easy to understand!!! thanks for all your efforts :)
sure
one of the best explanation videos. Clear as always, thank you
thanks
Thanks mate you are the best! Very easy to understand!
Man! You rock ❤️, you have exceptional teaching capabilities
thx
I struggle to understand iterative approaches towards dp problems. your video was great help! thanks ben!
Love your videos! Very easy to understand! Thank you!
So glad!
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.
THE BEST explanation I've seen ! Awesome !
i appreciate your passion, best explanation and grid for ways to make change
You are saving my time of solving this problem by myself! Thank you ^^
You should first try by yourself, then you should watch solutions.
OMG this is the best explanation!! Thank you!
Hey , I really loved the way you explain. Thank you sir !
thanks and sure
Wow ! finally someone explained how the tabular method works. Thanks :)
Best explanation one can find. Keep it up brother!!!
Thanks
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've looked at a bunch of explanations for how to solve this. Yours is by far the best explanation.
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 😀
Every video is so clear!
ye
Couldn't have explained it better...respect man!
thx
Great Video and I like that passionate vibe in your video!!
thx
POG dude
thx
Magnificent explanation!
Sir,keep it up!
ok
Awesome explanation you just nailed it!! Thanks.
ye
You're a Legend Man!
im normal
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.! ❤️
This guy is just brilliant. Superb job brother
Eh, I'm ok
Amazing Explanation!
thanks
God bless you for this clear explanation I was struggling for hours
You are great bro !!!
Thank you for lesson. 👏👏👍👍👍
sure
thank you. this video made everything clear for me
How can someone think like this dude, amazing.
im normal
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
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
You are a fabulous teacher, crystal clear, thank you so much!
Awesome!
A great way of explaination!
Brilliant, as always. Best explanation on RUclips. PS Nice that the whiteboard is not reflective!
thanks - ah true
Awesome explanation... I just like the way you present the problem thinking approach 👍💯
thx
You sir just gained a sub :) Loved your video . Please add more content on major interview problems .
working on it
Great explanation! Thank you...
sure
BEST EXPLANATION EVER!
This explaination is damn genius! Love it!
I love you ! I love your explaining ! crystle clear!
thanks
Thanks you bro,for making such a great video,in no words i can be more thankful to you,🙏🙏🙏
ye
This is such a clear explanation...thanks a lot. The best video on coin combinations explanation.👍
sure!
You have made these problems soooooo easy to understand!!!
Very Well Explained bruh!!
thanks
Most helpful explanation. Thanks a lot.
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
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
Best explanation. Clear, concise. Thanks 👍
Thank you so much!! Love from India.
Thanks for adding Tushar!
lol, old video, I was weird
Thanks bro, was really useful.
sure
U just nailed it ! 😁
haha thanks
I love the way how he is teaching :D.....thank you
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
Thanks for the nice explanation 💯