The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode)
HTML-код
- Опубликовано: 4 дек 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 climbing a staircase. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? (n is always a positive integer).
This is a classic problem. Let us tackle it thoroughly, there are many ways to do this that form the basis for how we do other problems bottom up with a DP table or top down with memoization.
The key with a problem like this is to instantly recognize that this turns into a series of subproblems, it is very similar to the Fibonacci sequence calculations.
Approach 1 (Top Down Recursion w/o Memoization)
Example:
n = 4
Let f(n) be the number of ways to climb n steps if we can take 1 or 2 steps.
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
Base case: f(0) = 1 and f(any negative number) = 0
Notice that we are resolving subproblems that we already have an answer to and hence we are wasting time.
Complexities
Time: O( 2 ^ n )
Each recursive call can spawn 2 more calls, depth of the recursion tree is n. This is a loose bound, a tighter one is around O( 1.62 ^ n )
Space: O( n )
Call stack max depth. Max depth of the recursion tree goes n calls deep.
Approach 2 (Use Memoization On Top Down)
Memoization: An optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Dynamic programming is all about storing the answers to previous sub-problems to speed up our runtimes by avoiding repeating work that has already been done.
Complexities
Time: O( n )
We cancel out many of the repeated calls that we might have made leading to us to have a linear time complexity.
Space: O( n )
Call stack max depth. And we will still have the dp table.
Approach 3 (Dynamic Programming Array)
DP is all about caching the answers to previous work and using it in current work.
dp[n] denotes the number of ways to climb n steps if we can take 1 or 2 steps.
dp[n] = dp[n - 2] + dp[n - 1]
The answer to n is the sum of the answer between two things:
our last step to n is 2 long
our last step to n is 1 long
Base Cases: dp[1] = 1 and dp[2] = 2
Complexities
Time: O( n )
A for loop making n - 2 iterations
Space: O( n )
We will be holding n + 1 entries in a dp array
Approach 4 (Fibonacci Number)
We notice that this is just the Fibonacci series. We can just use local variables to keep track of the items 1 and 2 behind where we stand.
Complexities
Time: O( n )
Still solve up to n subproblems.
Space: O( 1 )
No more dp array, we just use constant local variables
All other approaches are esoteric and are not practical in an interview, these include:
Using Binets Method & matrix multiplication
Using the mathematical, non-recursive, version of the Fibonacci Formula
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
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
I always come back to you and Tushar for clear explanations that make sense and are accessible
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!
The recursion tree at the beginning is spot on! thank you!
sure
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
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
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
Really love the logical flow of the teaching, it helped me! Thank you!
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.
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.
watched at least 4 videos about this problem, this is the first one that actually makes sense.
Great! You are one of the best teachers on youtube.
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.
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 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
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!
Awesome, Nothing beats your "falling egg , find pivotal floor" problem explanation...
thx
Finally, an explanation that makes sense.
yo
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 video was honestly so helpful. Solved the problem first try.
nice
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"
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
The best explanations(for different tasks) I have found 👏🏻
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
This one is the best explanation for this problem I have ever seen... 🔥🔥🔥
This is by far the best explanation! Thanks buddy!
BEST video I have seen on this. TY
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.
Watched a couple of your videos. Super insightful and well taught! Many thanks.
nice
I really liked the way you explain. Thanks!
sure
you made it so simple to understand for me. Thank you
nice.
Awesome explanation dude. I was trying to avoid this topic like forever. This is super cool. Thanks a ton!
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
Thank you so much, I did not catch before what was the purpose of memorization. You have explained it very well !!
sure
"We're gunna keep expressing *shakas emphatically* our decisions" xD love it
lmao something is wrong with me
Thanks a lot, finally understand how it works!!
Awesome explanation, I am not afraid of DP anymore :)
nice - Ben
Thanks a lot for strengthening my concepts.
Love how u break things down into subproblems 😅 great work dude
thx
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...
Thank you so much, you always make difficult looking problems, easy. 🧡 from India.
this man is awesome. thank you so much for this!
why this video has not million hits? he is too good
thanks.
Amazing explanation and intro to these sort of algorithms. Congrats!! :D
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
i wish u were my teacher when i studied software engineering 14 years back
You just got a new subscriber. Thank you!
sure
Amazing video, found it in the Leetcode discussions section, subbed !
Welcome. I am honored.
Great explanation for this problem!
superb!!! superb!!great work
Thank you! Cheers!
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.
Thank you!! This video was really helpful!
sure
Holy shit dude, you gave *the best* explanation! Thanks a lot!!
thanks
oh finally I got it!! Thanks a lot!!
sure!
Great explanation! Thank you very much!
Of course. Thank you for watching.
what a nice intro for dp
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!
bro you are too good
thx
Follow-up: Return the steps
!!!!!!!!!!!!!
your a cool guy man thank you for everything
sure!
8:54 Loved the way you explained recursion lol
what i do
Good one
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).
Back To Back SWE this comment too helped a lot , thanks
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
Great explanation man :)
Great explanation 🙏🙏🌼
Thanks for the video!
sure
Thanku so much for the explanation :)
Great explanation!
Quality content ..Thankyou so much
sure
Good luck, you get really cool
no u
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
Dude you're awesome!!!
no you are awesome
@@BackToBackSWE dude i was just seeing your knapsack video and your comment popped up lol!!!
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
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
Thank you so much !!
great explanation :)
Awesome, man!!!
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 (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?
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)?
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)?
OMG , this is awesome , thanks a lot!!!! , SUBSCRIBED
thanks
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!
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
Dude ❣️ best explanation
thanks
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.
Thank you!
I know this isn't really the point of the vid, but how did you calculate the exact bound (theta) @11:56?
Great video! you just got another sub! Keep it going!
thanks....oh...and...hey
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 😀
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