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.
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 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!
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!!!!
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}
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!
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.
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.
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!
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
@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!!
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]
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.
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 :)
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
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
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
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.
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
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 ❤
Hello Ben, please could you explain the line: table[row][col-coins[row-1]] from your whitboard. I know this is the logic for what you do when you use choose to use the current denomination in question and SHIFT LEFT instead of going up but I'm not sure specifically how the coins[row-1] section of the above logic works because the way you do it in the video is just coins located at (Current Amount - Denomination in question) without shifting the row.
Micheal, I understood your query So, if we do not use the coin, then we do not subtract the sum amount (because we do not use the coin), in the event when we use the coin, then our sum also decreases by that coin amount
Adding to @Sushree Moharana , the reason why the pattern for choosing a coin is table[row] [col - coins[row - 1] ] instead of table[row] [col - coins[row] ] is because we are accounting for the no coins row (the first row in the table) we added. Remember it was not explicitly an entry in the original coins array. Also don't confuse using the two equations at the edge of the table (first row and first column), they are initial conditions we start with for the dynamic problem solution. They are like the base cases in recursion. @Michael Chan
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.
Notice that a generating function also works! we can use an infinite number of 1p, 2p and 5p so (1+x+x^2+x^3+x^4+x^5...)(1+x^2+x^4...)(1+x^5...) and expanding only exponents of x^5 gives 4x^5 = 4 ways :>
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!
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!
I thought of buying the premium version but could not find this problem listed in your problems list. I could find only the (coin change 1 leetcode version)
Hi, great video, super detailed and easy to follow! I have one question though: For the minimum coin change question, you didn't split up the subproblems the way you are doing it now. Would the solution path you are following in this video be viable to solving the problem you solved in the fewest coin change problem you had in the other video? And if so, why?
Thanks and no it wouldn't, the subproblems here are different. While this is about the inclusion and exclusion of the ability to use a certain coin at different amounts - The Coin Change Problem is about just trying coins at each amount with no exclusion.
@@BackToBackSWE ohhhhhh ok, gotcha! How did you determine that exclusion played a part in your solution path? Did you just see that it was a combination problem and immediately thought exclusion?
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.
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
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.
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!
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
@@lifeofbarkin 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!!!!
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
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 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
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
Where was this guy during my days on campus. Man, I'm impressed. Thank you
haha, hey
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.
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
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
Explanation is very clear, thank you very much for providing better than any other paid content for free .
sure - it is what we do.
@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
Understood it for the very first time. Thanks for the repeated and clear explanation. Loved it man.
nice
I've looked at a bunch of explanations for how to solve this. Yours is by far the best explanation.
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!
One of the most clear and thoughtful explanations on the subject, thank you for spreading your knowledge, you are an excellent prof!
Beautiful, why can't my algo teacher be this good 😂
haha yeah
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 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 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 love the way you explain stuffs so easily. I was way too confused with this approach before watching this video :) Love ya!!
Wow! Your channel is a gold mine.
indeed.
I needed to watch this video like over and over and over and read about dynamic programming again.
Couldn't have explained it better...respect man!
thx
Thank you so much for explaining this problem ;). I'm new to these tough coding problems. But this video made it so understandable.
sure
one of the best explanation videos. Clear as always, thank you
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
Best explanation I found about this Coin Change problem, focusing on the subproblem... awesome.! ❤️
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.
Best explanation one can find. Keep it up brother!!!
Thanks
Your explaining power is very appreciable.Nice video.
hahaha thanks
I wish I could subscribe again, that's how good this channel is!
thx
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
Wow ! finally someone explained how the tabular method works. Thanks :)
your explanation is really good and easy to understand...this is really helpfull please make more videos like this...
thanks
THE BEST explanation I've seen ! Awesome !
i appreciate your passion, best explanation and grid for ways to make change
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
This is such a clear explanation...thanks a lot. The best video on coin combinations explanation.👍
sure!
Dude, thank you so much for your videos. You are such a natural teacher! : )
sure and thanks.
This guy is just brilliant. Superb job brother
Eh, I'm ok
God bless you for this clear explanation I was struggling for hours
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 😀
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
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
I struggle to understand iterative approaches towards dp problems. your video was great help! thanks ben!
best explanation to a dp problem i have ever seen.
ye
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
I love the video as well as the fact that you always like viewers comment.
yeah lol - I read everything
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
How can someone think like this dude, amazing.
im normal
Magnificent explanation!
Sir,keep it up!
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.
Hello Ben, please could you explain the line: table[row][col-coins[row-1]] from your whitboard.
I know this is the logic for what you do when you use choose to use the current denomination in question and SHIFT LEFT instead of going up but I'm not sure specifically how the coins[row-1] section of the above logic works because the way you do it in the video is just coins located at (Current Amount - Denomination in question) without shifting the row.
I don't remember to be honest. I'd need a refresher, I shot this long ago.
Micheal, I understood your query
So, if we do not use the coin, then we do not subtract the sum amount (because we do not use the coin), in the event when we use the coin, then our sum also decreases by that coin amount
Adding to @Sushree Moharana , the reason why the pattern for choosing a coin is table[row] [col - coins[row - 1] ] instead of table[row] [col - coins[row] ] is because we are accounting for the no coins row (the first row in the table) we added. Remember it was not explicitly an entry in the original coins array. Also don't confuse using the two equations at the edge of the table (first row and first column), they are initial conditions we start with for the dynamic problem solution. They are like the base cases in recursion. @Michael Chan
everyone can be coder , if not they are missing a teacher like u
yes
I love you ! I love your explaining ! crystle clear!
thanks
Great Video and I like that passionate vibe in your video!!
thx
Man! You rock ❤️, you have exceptional teaching capabilities
thx
Bravo super clean explanation, one note I think for [] 0 - we can set it as 0 and it will make more sense
thx
Best explanation. Clear, concise. Thanks 👍
I love the way how he is teaching :D.....thank you
amazing how well you teach!! Thanks for great work you do!
great video dude...was stuck on this one for the whole day!!
thanks.
BEST EXPLANATION EVER!
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
Great explanation! Thank you...
sure
Thank you so much!! Love from India.
God bless this man for his videos
Simply awesome dude ! Keep going ! Really helps having your videos!!
will do
Notice that a generating function also works! we can use an infinite number of 1p, 2p and 5p so (1+x+x^2+x^3+x^4+x^5...)(1+x^2+x^4...)(1+x^5...) and expanding only exponents of x^5 gives 4x^5 = 4 ways :>
Awesome explanation... I just like the way you present the problem thinking approach 👍💯
thx
You have made these problems soooooo easy to understand!!!
you make these problems easy to understand!!! thanks for all your efforts :)
sure
Best teacher superb explanation
thx
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
Sir please make more videos on dynamic programming
Data structures and algorithms
It will help lot of students.
Your videos are very good
ok
Love your videos! Very easy to understand! Thank you!
So glad!
I just Have a doubt here is it possible to return all the possible combinations in a list using this dp approach? Can anyone help me with this?
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
I thought of buying the premium version but could not find this problem listed in your problems list. I could find only the (coin change 1 leetcode version)
yes - we haven't ported all problems over and have some tabled for a reshoot
Hi, great video, super detailed and easy to follow! I have one question though: For the minimum coin change question, you didn't split up the subproblems the way you are doing it now. Would the solution path you are following in this video be viable to solving the problem you solved in the fewest coin change problem you had in the other video? And if so, why?
Thanks and no it wouldn't, the subproblems here are different. While this is about the inclusion and exclusion of the ability to use a certain coin at different amounts - The Coin Change Problem is about just trying coins at each amount with no exclusion.
@@BackToBackSWE ohhhhhh ok, gotcha! How did you determine that exclusion played a part in your solution path? Did you just see that it was a combination problem and immediately thought exclusion?
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 for adding Tushar!
lol, old video, I was weird
Thanks you bro,for making such a great video,in no words i can be more thankful to you,🙏🙏🙏
ye
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/
Thanks a lot for your videos Ben! I can see the subproblems in many DPs now!
can we have a top down dp approach(memoization) of this problem?
Yes
@@BackToBackSWE How?
please explain i am stuck at it.