Table of Contents: A Short Message From Our Sponsors 0:00 - 1:15 The Problem Introduction 1:15 - 3:25 Top-Down Approach (Without Memoization) 3:25 - 10:56 Duplication of Work: Why We Memoize 10:56 - 12:12 Pruning The Work Tree 12:12 - 14:06 The Bottom-Up Approach 14:06 - 17:18 Time & Space Complexities 17:18 - 18:40 Subscribe & Be My Friend 18:40 - 19:12 The code for this problem is in the description. Fully commented for understanding with both the top down and bottom approaches.
Quick question lol. You mention that you've been through EPI several times, did you follow the schedule in the beginning of the book? Or did you solve every problem in the book? How long did your first walkthrough take? I'm asking because I'm currently job hunting as a new grad. Thanks :)
This is the most clear explanation of this problem I have seen so far. In most other videos they take the bottom-up approach when they explain it, and it becomes confusing real quick. Drawing the recursion tree top-down was really helpful.
I totally agree with you that all of these problems have nothing to do with the day to day problems that software developers work on. Having been a software developer for 15+ years, mainly backend C++ code that runs on hundreds of servers, I honestly find asking dynamic programming questions (and similar) in interviews ridiculous. But as someone interested in maybe changing jobs, you have to know this stuff as all the big companies for some reason ask you these questions, not sure why. I think your and Tushar Roy's channel as well as actual practice on Leetcode are the best resources out there to practice for the larger companies that ask these types of problems. Thanks for all the work you are putting into this!
This is such a great explanation. I am a working software engineer, but really out of practice with some fundamentals. And I hardly think of problems of this nature during my day-to-day. This explanation made this problem look so much easier than my original wtf moment. Thank you!
Sean. This is Ben. It is an honor to have taught you this problem. The reason I do this is because of people like you I know that there are people in your position and my aim is to make your life a little easier because these problems suck. I hope you keep growing and keep succeeding.
Thanks for this video. Finally someone who can clearly explain top down vs bottom up DP. You are a great teacher man. Keep it up. You just saved me hours and hours of headache.
I feel out of RUclips you are the best explainer of dynamic programming. You break everything down into the simplest of things and keep it paced really well to make sure everybody understands.....Thanks for the video!!! U are a fantastic teacher dude
I got a similar question in one of my interview to return the total ways. Eg: totalWays(n, steps); eg: totalWays(3, [1, 2]) should return [[1, 1, 1], [2, 1], [1, 2]] . I started solving the question using dynamic programming . But in the middle I thought that i need to find all the ways. And all I could hear in my ears was someone shouting "whenever we have to find all possibilities or generate all, then we are dealing with a backtracking problem". And immediately jumped on the pattern of backtracking and solved the question the same way you taught in the video of permutation of string. Aced the interview like a boss with no mistakes
That branch cutting is very satisfying. This is my first video on this problem and is also the last video for the same. Thanks a lot for the amazing explanation. Cheers.
Like many working programmers, became one from one the job training not so much study and theory. But the theory and logic fascinate me now. Was able to write an algorithm C# that worked, once someone told me about the relationship to the Fibonacci sequence, but now I know WHY it relates to Fibonacci. Live and learn, love it, very intuitive, you're the man.
Great work! This is the only teaching material by far that explains the base case properly after reading hundreds of those that simply says "declaring F(0) = 1 is easier"
@@BackToBackSWE Hi, I am still slightly confused about f(0) = 1... how does doing nothing count as 1? Can I interpret there are three moves you can make like 0, 1 and 2 steps? Except 0 step won't get you anywhere forward
I notice myself getting so much better after watching many of your videos. Now in half of your videos I figure it out in a moment and say to myself "well that was kinda obvious"
I found it hard to start solving DP questions, but since I found out this channel it's much more intuitive! Wherever I've read about where to start and how to think when solving these kind of problems, nobody could explain thinking process better than you. Great job :)
As I always say 'the best explanation' I request you to make more and more videos like this .I will make sure all of my friends watch videos of your channel
@@BackToBackSWE haha, play on playaaaa :D Can I ask, how did you get started teaching Algorithms? I went from Biology teacher to SWE a couple of years ago, but Im trying to find a way to get back into teaching!
Just wanted to say a quick thank you! Had a Data structure and algorithm class this semester and you videos helped me so much understanding how you need to think when solving problems
I know this wasn’t your intention because how could it have been, but I just had a revelation about myself and why I’ve been struggling with interview questions thanks to you
Two things: 1. the time complexity is actually O(mn) where m is the number of possible steps sizes (in this case 1,2) 2. the O(n) time complexity sounds good but you should have mentioned that it is actually exponential to the input value (of 6 in the example) Great videos man
Thank you sir. With the help of your explanation I was able to code the problem in both the ways I.e., top down and bottom up. I have a question. What is the difference between Memorization and Dynamic Programming as they both are used to save us from computing the same sub problem again. Thank you sir...
converting to code in python(works only for n=6): n=6 list1=[1,1,1,1,1,1,1] for i in range(2,n+1): list1[i]=list1[i-2]+list1[i-1] print(list1[n]) JUST WORK IT OUT FOR DIFFERENT VALUES BY ALTERING THE 'N' VALUE AND LIST SIZE*
This was excellent, you are a rockstar! Just one follow up question: Can you give us an example where one approach is significantly better than the other one?
White boarding goes a long way! as soon as you broke down working from the top and subtracting 1 step, subtracting 2 steps, and the total of that sum gives you how many steps you need to take--it CLICKED! Thanks
Thank you very much, your goal deserves nothing but admiration! Out of those many videos on the topic out there, I find yours absolutely the best! Can you please help me understand something: 1. This problems at a first glance is very similar to the coin change problem. With the key difference being that with coins order doesn't matter (hence we have less combinations), while with the stair order matters as the same set of steps could yield different ways of climbing (permutations). Understanding that I'm still not catching where exactly this difference is accounted for in those two algorithms. Where should I look? 2. I missed the intuition behind the "+" operation (n = (n-1) + (n-2)). When you do add those, it's easy to see the Fibonacci sequence but I do not understand why we should use the '+' there in the first place. In other words I seem to have missed the intuition on why the number of ways to climb N steps equals the number of ways to climb n-1 steps plus n-2 steps. I'd appreciate your help with those) .
1.) Consider that what we are really saying is...the answer to dp[i] is the cumulation of all the possible ways if the LAST step we take is 1 step or 2 steps. It is very similar to the coin change problem, just the formatting changes. The fundamental reasoning is the same. So consider that...from any point...our last step uniquely identifies the path to where we stand...which is 'i' steps left to consume. This is why order does matter. That last step makes any path up to our current destination unique. That is the distinction. 2.) The intuition is the "last step" idea. The unique "footprint" to a path is the last step taken to where we are. So to get to n we have 2 unique choices that differentiate our progress up to that point....1 step and 2 step... as the final step. This is the intuition...and consider that we drill to base cases where we KNOW the answer. (and these base cases are like a net we can make as wide as possible, or as shallow as possible). When I add dp[i -1] and dp[i - 2] I am saying that the answer to the subproblem dp[i] IS THE SAME as the sum of ALL the ways if my last step is a 1 step or a 2 step. I'm kinda mentally tired from schoolwork that I got behind on so the above may not be enough for you to really understand this, if you have any questions continue asking, I will answer (and hopefully be less mentally foggy later).
One of the interesting things to note here is that in case if you only have the option of taking 1 or two steps back it boils down to finding the nth Fibonacci number because the current value is the sum of the previous two with the base case and the number of ways to take the first step being 1. So in case you want to impress your friends you can say hey if you climb these stairs by taking either one step or two, the number of ways to do so is the nth Fibonacci number where n is the number of steps.
This is a great explanation. I also want to understand how to handle the same question with some constraints thrown in Could you please help me understand how to proceed with a variant of this problem? The question is as follows: I need to reach n stairs by taking 1 step or 2 step or 3 steps. However, I can only take 3 steps at most b times. What are the total number of ways I can reach the n steps?
This (and many videos similar to it) establish the fact that knowing how many unique ways to N stairs is simply adding the unique ways to N-1 to the unique ways to N-2. My question and what I'm confused about is, how do we already know this? Is this is a common/expected known statistic or probability thing?
For me it wasn't clear why the solution to 6 would be the solution to 4 + 5. But I finally got it and just putting the logic here if others don't get it. You need to add 2 steps to all the solutions in 4 to get 6 steps. And you need to add 1 step to all the solutions in 5 to get 6 steps. The combination of those solutions are the answer to 6.
if DP is hard to understand at the first place, you can solve it by recursion. The recursive function will return iff it reaches the leaves of the tree, and the parent of the recursion tree will see the # of valid leaves. ff you do 4+5, after finishing the recursion, you will get # of all child nodes traversed not only the leaves
4:45 It always seems to me that the sum of the steps to get to 4 and the steps to get to 5 is either not enough (depending on how I look at it), because I haven't gotten to 6, or too much, because if I add 4 and 5 I get 9. I still have to think about it. I mean, from the root, you took 1 or 2 steps. So why aren't you adding those steps back in? The tree helped a lot. I understand the dp but I have trouble understanding the logic. I'm working on a problem where you can take 1, 2, or 3 steps, and whenever I figure it myself, I'm off by one. Having code would be incrementally better but then you have to decide on a language and you won't please everybody. But your work is far above geeksforgeeks. I don't know how they got on top of google (wouldn't be surprised if they worked there and know the algorithm). I always search with their name excluded. update: It finally made sense. I drew out the first steps (3 for my problem. [1] | [1,1],[2] | [1,1,1],[1,2],[2,1],[3] and it was easy to see that I would add 3, 2, or 1 steps to make 4. And then, it's induction. I used a list and passed all my tests. Yay!
Google ranked them overtime and they have thousands of trafficked pages. Content on the internet doesn't have to be good to succeed (though it helps). It just has to be "there" for a long time.
This may sound dumb, but from a conceptual standpoint, why is the number of ways to reach a certain stair the sum of the ways you can reach the current stair -1 and -2 (assuming only 1 and 2 steps)? Like shouldnt we add a +1 because we are technically adding a new way to get to up to the current stair?
No ur gud - there is no dumb. If you are attempting critical thinking and trying hard there is only improvement. And I get your angle, but the idea is to consider everything behind even step -1 and step -2 because those have dynamic answers as well. You are thinking along the right lines.
@@BackToBackSWE But what about even at lets say, step 3. Why is the number of ways to get to step 3, the number of ways you can go up step 2 + number of ways you can go up step 1? Like from a conceptual standpoint, why does that make sense? Like why dont we add number of ways to go up step 1 + number of ways to go up step 2 + 2 (because either 1 step or 2 steps)?
Can you explain in Bottom up approach, .i.e Tabulation, the advantage of storing values in Tables. Is it because any future execution of the function, will save time by not needing to calculate from the base cases. For example, Once F(6) = 13 is calculated, For F(8) I just need to calculate F(7), instead of calculating again from F[0] to F[7] ??
"Is it because any future execution of the function, will save time by not needing to calculate from the base cases." Yes. The code won't solve paths already solved, thus saving time.
All right, I have watched many of your videos, and I always have one same question. I need to ask you now...so, can you tell me what exactly your filming camera is? I really like the shot! Thx again!
@@BackToBackSWE wow.. Thxs 4 quick reply.. I'm just going through recursion videos... Your bottom approach & top down approach is just awesome.. Very easy to understand.. Thank you very much
No, it just helps with indexing. Our answer ends up at index n instead of n - 1. Adding the 0 at the front pushes all elements to the right by 1. + 1 to each index.
Table of Contents:
A Short Message From Our Sponsors 0:00 - 1:15
The Problem Introduction 1:15 - 3:25
Top-Down Approach (Without Memoization) 3:25 - 10:56
Duplication of Work: Why We Memoize 10:56 - 12:12
Pruning The Work Tree 12:12 - 14:06
The Bottom-Up Approach 14:06 - 17:18
Time & Space Complexities 17:18 - 18:40
Subscribe & Be My Friend 18:40 - 19:12
The code for this problem is in the description. Fully commented for understanding with both the top down and bottom approaches.
I am going to falling in love with you.. Perfect!
ye
2:38 golden "Tushar take it away"
my b, old video
Finally, an explanation that makes sense beyond intuition. I really appreciate this
great and thanks
I just discovered your channel like a few days ago but these are so good. Such a clear explanation and walkthrough. You're killing it, dude!
Quick question lol. You mention that you've been through EPI several times, did you follow the schedule in the beginning of the book? Or did you solve every problem in the book? How long did your first walkthrough take? I'm asking because I'm currently job hunting as a new grad. Thanks :)
Thanks!
This is the most clear explanation of this problem I have seen so far. In most other videos they take the bottom-up approach when they explain it, and it becomes confusing real quick. Drawing the recursion tree top-down was really helpful.
Thanks! why dont you subscribe to our exclusive DSA course and avail 30% discount for some great content b2bswe.co/3HhvIlV
The recursion tree at the beginning is spot on! thank you!
sure
I totally agree with you that all of these problems have nothing to do with the day to day problems that software developers work on. Having been a software developer for 15+ years, mainly backend C++ code that runs on hundreds of servers, I honestly find asking dynamic programming questions (and similar) in interviews ridiculous. But as someone interested in maybe changing jobs, you have to know this stuff as all the big companies for some reason ask you these questions, not sure why. I think your and Tushar Roy's channel as well as actual practice on Leetcode are the best resources out there to practice for the larger companies that ask these types of problems. Thanks for all the work you are putting into this!
Thanks for this!
I always come back to you and Tushar for clear explanations that make sense and are accessible
This is such a great explanation. I am a working software engineer, but really out of practice with some fundamentals. And I hardly think of problems of this nature during my day-to-day. This explanation made this problem look so much easier than my original wtf moment. Thank you!
Sean. This is Ben. It is an honor to have taught you this problem. The reason I do this is because of people like you
I know that there are people in your position and my aim is to make your life a little easier because these problems suck. I hope you keep growing and keep succeeding.
Thanks for this video. Finally someone who can clearly explain top down vs bottom up DP. You are a great teacher man. Keep it up. You just saved me hours and hours of headache.
Thanks.....and.................................hi
watched at least 4 videos about this problem, this is the first one that actually makes sense.
I don't know why but as I am preparing for my interview, I keep coming back to this channel every now and then. Great work!
cuz we cool
I feel out of RUclips you are the best explainer of dynamic programming. You break everything down into the simplest of things and keep it paced really well to make sure everybody understands.....Thanks for the video!!! U are a fantastic teacher dude
Yes - because I understand it really well and can articulate it in a way a general person can understand it.
I got a similar question in one of my interview to return the total ways.
Eg: totalWays(n, steps); eg: totalWays(3, [1, 2]) should return [[1, 1, 1], [2, 1], [1, 2]]
. I started solving the question using dynamic programming . But in the middle I thought that i need to find all the ways. And all I could hear in my ears was someone shouting "whenever we have to find all possibilities or generate all, then we are dealing with a backtracking problem". And immediately jumped on the pattern of backtracking and solved the question the same way you taught in the video of permutation of string. Aced the interview like a boss with no mistakes
nice nice
Really love the logical flow of the teaching, it helped me! Thank you!
That branch cutting is very satisfying. This is my first video on this problem and is also the last video for the same. Thanks a lot for the amazing explanation. Cheers.
Like many working programmers, became one from one the job training not so much study and theory. But the theory and logic fascinate me now. Was able to write an algorithm C# that worked, once someone told me about the relationship to the Fibonacci sequence, but now I know WHY it relates to Fibonacci. Live and learn, love it, very intuitive, you're the man.
Great work! This is the only teaching material by far that explains the base case properly after reading hundreds of those that simply says "declaring F(0) = 1 is easier"
Thank you. I'm honored that you even watched this.
@@BackToBackSWE 5 months later still the only tutorial that makes sense top-down or bottom-up :'D
@@lamsaitat haha, yoyo
@@BackToBackSWE Hi, I am still slightly confused about f(0) = 1... how does doing nothing count as 1? Can I interpret there are three moves you can make like 0, 1 and 2 steps? Except 0 step won't get you anywhere forward
This man is amazing wow, I couldn't for the life of me understand this problem before and now its crystal clear! I was blind and now I see!
glad it helped
Great! You are one of the best teachers on youtube.
I notice myself getting so much better after watching many of your videos. Now in half of your videos I figure it out in a moment and say to myself "well that was kinda obvious"
I found it hard to start solving DP questions, but since I found out this channel it's much more intuitive! Wherever I've read about where to start and how to think when solving these kind of problems, nobody could explain thinking process better than you. Great job :)
thx
As I always say 'the best explanation' I request you to make more and more videos like this .I will make sure all of my friends watch videos of your channel
Nice! I will be releasing a course in 1-2 months, stay tuned
This one is the best explanation for this problem I have ever seen... 🔥🔥🔥
Awesome, Nothing beats your "falling egg , find pivotal floor" problem explanation...
thx
Finally, an explanation that makes sense.
yo
You are an excellent teacher man! I taught high school for 6 years and game recognize game, you have a talent :D
Hahahahaha thanks
I love the game!!!!
@@BackToBackSWE haha, play on playaaaa :D Can I ask, how did you get started teaching Algorithms? I went from Biology teacher to SWE a couple of years ago, but Im trying to find a way to get back into teaching!
This video was honestly so helpful. Solved the problem first try.
nice
The best explanations(for different tasks) I have found 👏🏻
I LOVE YOU ❤️! I'll be your patreon when I get a job. Thanks!
No worries, just get the job haha. And love you too.
"We're gunna keep expressing *shakas emphatically* our decisions" xD love it
lmao something is wrong with me
BEST video I have seen on this. TY
Just wanted to say a quick thank you! Had a Data structure and algorithm class this semester and you videos helped me so much understanding how you need to think when solving problems
alright I am here to say WOW, that tree helped me out so much... like seriously amazing. I never have thought of it like that before
great
This is by far the best explanation! Thanks buddy!
Thank you so much, you always make difficult looking problems, easy. 🧡 from India.
I know this wasn’t your intention because how could it have been, but I just had a revelation about myself and why I’ve been struggling with interview questions thanks to you
lol nice
revelation? what was that? I am curious...I might have the same revelation too if you let us know. :D
@@blasttrash yo
@@BackToBackSWE yo, whats up. Hope you have a nice weekend. :D
@@blasttrash The weekend just happened
Love how u break things down into subproblems 😅 great work dude
thx
Watched a couple of your videos. Super insightful and well taught! Many thanks.
nice
I really liked the way you explain. Thanks!
sure
Awesome explanation dude. I was trying to avoid this topic like forever. This is super cool. Thanks a ton!
Thank you so much, I did not catch before what was the purpose of memorization. You have explained it very well !!
sure
Such a great explanation.Instant subscribe.
welcome friend
Subscribing after watching the steps problem. Thank you for your efforts. Please keep educating us.
ok thanks
Amazing video, found it in the Leetcode discussions section, subbed !
Welcome. I am honored.
i wish u were my teacher when i studied software engineering 14 years back
why this video has not million hits? he is too good
thanks.
Thanks a lot, finally understand how it works!!
Thank you!! This video was really helpful!
sure
you made it so simple to understand for me. Thank you
nice.
this man is awesome. thank you so much for this!
Two things:
1. the time complexity is actually O(mn) where m is the number of possible steps sizes (in this case 1,2)
2. the O(n) time complexity sounds good but you should have mentioned that it is actually exponential to the input value (of 6 in the example)
Great videos man
I don't remember this video much so can't validate 1, and ok for 2. And ok
Yeah both the points are true.
Awesome explanation, I am not afraid of DP anymore :)
nice - Ben
Amazing explanation and intro to these sort of algorithms. Congrats!! :D
Great explanation for this problem!
You just got a new subscriber. Thank you!
sure
Holy shit dude, you gave *the best* explanation! Thanks a lot!!
thanks
Thanks a lot for strengthening my concepts.
Thank you sir. With the help of your explanation I was able to code the problem in both the ways I.e., top down and bottom up. I have a question. What is the difference between Memorization and Dynamic Programming as they both are used to save us from computing the same sub problem again. Thank you sir...
superb!!! superb!!great work
Thank you! Cheers!
oh finally I got it!! Thanks a lot!!
sure!
converting to code in python(works only for n=6):
n=6
list1=[1,1,1,1,1,1,1]
for i in range(2,n+1):
list1[i]=list1[i-2]+list1[i-1]
print(list1[n])
JUST WORK IT OUT FOR DIFFERENT VALUES BY ALTERING THE 'N' VALUE AND LIST SIZE*
what lol
Great explanation! Thank you very much!
Of course. Thank you for watching.
Great explanation 🙏🙏🌼
This was excellent, you are a rockstar! Just one follow up question: Can you give us an example where one approach is significantly better than the other one?
thanks and I dont remember this video much tbh
@@BackToBackSWE No problem, I completely understand. Thanks for your response. Please stay safe!
what a nice intro for dp
White boarding goes a long way! as soon as you broke down working from the top and subtracting 1 step, subtracting 2 steps, and the total of that sum gives you how many steps you need to take--it CLICKED! Thanks
sure
your a cool guy man thank you for everything
sure!
Great explanation man :)
Thank you very much, your goal deserves nothing but admiration! Out of those many videos on the topic out there, I find yours absolutely the best!
Can you please help me understand something:
1. This problems at a first glance is very similar to the coin change problem. With the key difference being that with coins order doesn't matter (hence we have less combinations), while with the stair order matters as the same set of steps could yield different ways of climbing (permutations). Understanding that I'm still not catching where exactly this difference is accounted for in those two algorithms. Where should I look?
2. I missed the intuition behind the "+" operation (n = (n-1) + (n-2)). When you do add those, it's easy to see the Fibonacci sequence but I do not understand why we should use the '+' there in the first place. In other words I seem to have missed the intuition on why the number of ways to climb N steps equals the number of ways to climb n-1 steps plus n-2 steps.
I'd appreciate your help with those) .
1.) Consider that what we are really saying is...the answer to dp[i] is the cumulation of all the possible ways if the LAST step we take is 1 step or 2 steps. It is very similar to the coin change problem, just the formatting changes. The fundamental reasoning is the same. So consider that...from any point...our last step uniquely identifies the path to where we stand...which is 'i' steps left to consume. This is why order does matter. That last step makes any path up to our current destination unique. That is the distinction.
2.) The intuition is the "last step" idea. The unique "footprint" to a path is the last step taken to where we are. So to get to n we have 2 unique choices that differentiate our progress up to that point....1 step and 2 step... as the final step. This is the intuition...and consider that we drill to base cases where we KNOW the answer. (and these base cases are like a net we can make as wide as possible, or as shallow as possible). When I add dp[i -1] and dp[i - 2] I am saying that the answer to the subproblem dp[i] IS THE SAME as the sum of ALL the ways if my last step is a 1 step or a 2 step.
I'm kinda mentally tired from schoolwork that I got behind on so the above may not be enough for you to really understand this, if you have any questions continue asking, I will answer (and hopefully be less mentally foggy later).
Back To Back SWE this comment too helped a lot , thanks
Great video! you just got another sub! Keep it going!
thanks....oh...and...hey
One of the interesting things to note here is that in case if you only have the option of taking 1 or two steps back it boils down to finding the nth Fibonacci number because the current value is the sum of the previous two with the base case and the number of ways to take the first step being 1. So in case you want to impress your friends you can say hey if you climb these stairs by taking either one step or two, the number of ways to do so is the nth Fibonacci number where n is the number of steps.
yes
This is a great explanation. I also want to understand how to handle the same question with some constraints thrown in Could you please help me understand how to proceed with a variant of this problem?
The question is as follows: I need to reach n stairs by taking 1 step or 2 step or 3 steps. However, I can only take 3 steps at most b times. What are the total number of ways I can reach the n steps?
Sounds like that could be solved by restricting the recursion & keeping state on the number of 3's used so far
This (and many videos similar to it) establish the fact that knowing how many unique ways to N stairs is simply adding the unique ways to N-1 to the unique ways to N-2. My question and what I'm confused about is, how do we already know this? Is this is a common/expected known statistic or probability thing?
OMG , this is awesome , thanks a lot!!!! , SUBSCRIBED
thanks
For me it wasn't clear why the solution to 6 would be the solution to 4 + 5.
But I finally got it and just putting the logic here if others don't get it.
You need to add 2 steps to all the solutions in 4 to get 6 steps. And you need to add 1 step to all the solutions in 5 to get 6 steps. The combination of those solutions are the answer to 6.
oops
if DP is hard to understand at the first place, you can solve it by recursion. The recursive function will return iff it reaches the leaves of the tree, and the parent of the recursion tree will see the # of valid leaves. ff you do 4+5, after finishing the recursion, you will get # of all child nodes traversed not only the leaves
bro you are too good
thx
4:45 It always seems to me that the sum of the steps to get to 4 and the steps to get to 5 is either not enough (depending on how I look at it), because I haven't gotten to 6, or too much, because if I add 4 and 5 I get 9. I still have to think about it. I mean, from the root, you took 1 or 2 steps. So why aren't you adding those steps back in?
The tree helped a lot. I understand the dp but I have trouble understanding the logic. I'm working on a problem where you can take 1, 2, or 3 steps, and whenever I figure it myself, I'm off by one.
Having code would be incrementally better but then you have to decide on a language and you won't please everybody. But your work is far above geeksforgeeks. I don't know how they got on top of google (wouldn't be surprised if they worked there and know the algorithm). I always search with their name excluded.
update: It finally made sense. I drew out the first steps (3 for my problem. [1] | [1,1],[2] | [1,1,1],[1,2],[2,1],[3] and it was easy to see that I would add 3, 2, or 1 steps to make 4. And then, it's induction. I used a list and passed all my tests. Yay!
Google ranked them overtime and they have thousands of trafficked pages. Content on the internet doesn't have to be good to succeed (though it helps). It just has to be "there" for a long time.
Dude you're awesome!!!
no you are awesome
@@BackToBackSWE dude i was just seeing your knapsack video and your comment popped up lol!!!
Thanku so much for the explanation :)
Hey Ben, when do you recommend top down vs bottom up? To me bottom up always seems like the most easy to implement
Yeah, what you just said is true. I agree with that. I just have a knack for top down, not sure why. It is just cool.
Good stuff bro.
thanks
8:54 Loved the way you explained recursion lol
what i do
Dude ❣️ best explanation
thanks
Hello, thanks for the video, it was very informative. But how did you calculate the complexity being O(1.62^n)? How did you get O(2^n)?
Great explanation!
Thanks for the video!
sure
Quality content ..Thankyou so much
sure
I know this isn't really the point of the vid, but how did you calculate the exact bound (theta) @11:56?
Follow-up: Return the steps
!!!!!!!!!!!!!
This may sound dumb, but from a conceptual standpoint, why is the number of ways to reach a certain stair the sum of the ways you can reach the current stair -1 and -2 (assuming only 1 and 2 steps)? Like shouldnt we add a +1 because we are technically adding a new way to get to up to the current stair?
No ur gud - there is no dumb. If you are attempting critical thinking and trying hard there is only improvement.
And I get your angle, but the idea is to consider everything behind even step -1 and step -2 because those have dynamic answers as well. You are thinking along the right lines.
@@BackToBackSWE But what about even at lets say, step 3. Why is the number of ways to get to step 3, the number of ways you can go up step 2 + number of ways you can go up step 1? Like from a conceptual standpoint, why does that make sense? Like why dont we add number of ways to go up step 1 + number of ways to go up step 2 + 2 (because either 1 step or 2 steps)?
Awesome, man!!!
Good one
thanks
Good luck, you get really cool
no u
Can you explain in Bottom up approach, .i.e Tabulation, the advantage of storing values in Tables. Is it because any future execution of the function, will save time by not needing to calculate from the base cases.
For example, Once F(6) = 13 is calculated, For F(8) I just need to calculate F(7), instead of calculating again from F[0] to F[7] ??
"Is it because any future execution of the function, will save time by not needing to calculate from the base cases." Yes. The code won't solve paths already solved, thus saving time.
All right, I have watched many of your videos, and I always have one same question. I need to ask you now...so, can you tell me what exactly your filming camera is? I really like the shot! Thx again!
Canon Rebel T3i
@@BackToBackSWE Thanks for your reply! Have a nice day!
great explanation :)
Great video... But i didn't find any link in description for code.. Is it missed
Hi - the repository is deprecated, we only maintain backtobackswe.com now.
@@BackToBackSWE wow.. Thxs 4 quick reply.. I'm just going through recursion videos... Your bottom approach & top down approach is just awesome.. Very easy to understand.. Thank you very much
Great tutorial! One quick question, why we make our memo array size of n + 1? is it because we store one more 0 for n < 0?
No, it just helps with indexing. Our answer ends up at index n instead of n - 1. Adding the 0 at the front pushes all elements to the right by 1. + 1 to each index.
Great video! Thanks!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀