The Recursive Staircase - Top Down & Bottom Up Dynamic Programming ("Climbing Stairs" on LeetCode)

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 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

[@BackToBackSWE]

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.

[@aysesayn7938]

I am going to falling in love with you.. Perfect!

[@BackToBackSWE]

ye

[@queensfinezt]

2:38 golden "Tushar take it away"

[@BackToBackSWE]

my b, old video

[@ayodejiakinola7343]

Finally, an explanation that makes sense beyond intuition. I really appreciate this

[@BackToBackSWE]

great and thanks

[@TheChromeLegend]

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!

[@TheChromeLegend]

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 :)

[@BackToBackSWE]

Thanks!

[@narihanellaithy7726]

The recursion tree at the beginning is spot on! thank you!

[@BackToBackSWE]

sure

[@labs1]

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

[@qwarlockz8017]

I always come back to you and Tushar for clear explanations that make sense and are accessible

[@shaunvaughn3323]

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.

[@BackToBackSWE]

Thanks.....and.................................hi

[@_hello_5346]

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.

[@BackToBackSWE]

Thanks! why dont you subscribe to our exclusive DSA course and avail 30% discount for some great content b2bswe.co/3HhvIlV

[@mfkman]

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!

[@BackToBackSWE]

Thanks for this!

[@seanchon]

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!

[@BackToBackSWE]

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.

[@TheBarbaraMouse]

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 :)

[@BackToBackSWE]

thx

[@abcdeereijgfhd3215]

Great! You are one of the best teachers on youtube.

[@gimmeerkin2131]

The best explanations(for different tasks) I have found 👏🏻

[@shritishaw7510]

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.

[@sifatmoonjerin2479]

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!

[@BackToBackSWE]

cuz we cool

[@Gary1q2]

I feel out of KZbin 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

[@BackToBackSWE]

Yes - because I understand it really well and can articulate it in a way a general person can understand it.

[@krishnanigalye1173]

Awesome explanation dude. I was trying to avoid this topic like forever. This is super cool. Thanks a ton!

[@optionaltoaster1]

This is the video that finally made it click for me. I wrote out the sequence and realized it was the Fibonacci sequence, but I couldn't understand conceptually why that was until I heard your top down explanation. Thanks!

[@kirancoding1576]

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]

Nice! I will be releasing a course in 1-2 months, stay tuned

[@danielkashkett7040]

watched at least 4 videos about this problem, this is the first one that actually makes sense.

[@2tce]

Watched a couple of your videos. Super insightful and well taught! Many thanks.

[@BackToBackSWE]

nice

[@Finn-jp6pn]

I LOVE YOU ❤️! I'll be your patreon when I get a job. Thanks!

[@BackToBackSWE]

No worries, just get the job haha. And love you too.

[@ginasomara267]

BEST video I have seen on this. TY

[@smithcodes1243]

This is by far the best explanation! Thanks buddy!

[@venkateshn9884]

This one is the best explanation for this problem I have ever seen... 🔥🔥🔥

[@maximedero4270]

Thank you so much, I did not catch before what was the purpose of memorization. You have explained it very well !!

[@BackToBackSWE]

sure

[@davesmith5043]

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!

[@BackToBackSWE]

glad it helped

[@wilsonjiang8849]

Amazing video, found it in the Leetcode discussions section, subbed !

[@BackToBackSWE]

Welcome. I am honored.

[@arxci9402]

This video was honestly so helpful. Solved the problem first try.

[@BackToBackSWE]

nice

[@luisasanchez9267]

Amazing explanation and intro to these sort of algorithms. Congrats!! :D

[@josecunha6974]

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.

[@yashnanda4864]

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"

[@kuxnal]

this man is awesome. thank you so much for this!

[@shubhamuniyal2417]

Love how u break things down into subproblems 😅 great work dude

[@BackToBackSWE]

thx

[@matthewbuchholz7091]

"We're gunna keep expressing *shakas emphatically* our decisions" xD love it

[@BackToBackSWE]

lmao something is wrong with me

[@amithbk12man]

I really liked the way you explain. Thanks!

[@BackToBackSWE]

sure

[@SatyadeepRoat]

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

[@BackToBackSWE]

nice nice

[@rchukkapalli1]

Subscribing after watching the steps problem. Thank you for your efforts. Please keep educating us.

[@BackToBackSWE]

ok thanks

[@Arnott_me]

Thanks a lot, finally understand how it works!!

[@SK-lu7ci]

Awesome, Nothing beats your "falling egg , find pivotal floor" problem explanation...

[@BackToBackSWE]

thx

[@cooperwsu7206]

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

[@BackToBackSWE]

great

[@MacaroonL]

Thank you!! This video was really helpful!

[@BackToBackSWE]

sure

[@beteltadesse9803]

Great explanation. Thank you!

[@vineethm6930]

Thanks a lot for strengthening my concepts.

[@user-nf8tw8sk5t]

Awesome, man!!!

[@rajatjain7680]

you made it so simple to understand for me. Thank you

[@BackToBackSWE]

nice.

[@killeraloo3247]

Thank you so much, you always make difficult looking problems, easy. 🧡 from India.

[@PomboKad]

You just got a new subscriber. Thank you!

[@BackToBackSWE]

sure

[@lamsaitat]

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]

Thank you. I'm honored that you even watched this.

[@lamsaitat]

@@BackToBackSWE 5 months later still the only tutorial that makes sense top-down or bottom-up :'D

[@BackToBackSWE]

@@lamsaitat haha, yoyo

[@wtcxdm]

@@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

[@sapunovnik]

Great explanation! Thank you very much!

[@BackToBackSWE]

Of course. Thank you for watching.

[@talesfromthemidwest]

Finally, an explanation that makes sense.

[@BackToBackSWE]

yo

[@SoledadDelSol]

Great explanation for this problem!

[@tejasvigupta07]

Such a great explanation.Instant subscribe.

[@BackToBackSWE]

welcome friend

[@jyl4990]

Great video! you just got another sub! Keep it going!

[@BackToBackSWE]

thanks....oh...and...hey

[@shoco2]

Great explanation!

[@marceldegas]

You are an excellent teacher man! I taught high school for 6 years and game recognize game, you have a talent :D

[@BackToBackSWE]

Hahahahaha thanks

[@BackToBackSWE]

I love the game!!!!

[@marceldegas]

@@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!

[@bhargavsai2449]

superb!!! superb!!great work

[@BackToBackSWE]

Thank you! Cheers!

[@sandeeps7625]

OMG , this is awesome , thanks a lot!!!! , SUBSCRIBED

[@BackToBackSWE]

thanks

[@user-wf8lg1qk1s]

Awesome explanation, I am not afraid of DP anymore :)

[@BackToBackSWE]

nice - Ben

[@iamjavator4594]

Thank you so much !!

[@shiladryadak1541]

oh finally I got it!! Thanks a lot!!

[@BackToBackSWE]

sure!

[@kalusharma2201]

Holy shit dude, you gave *the best* explanation! Thanks a lot!!

[@BackToBackSWE]

thanks

[@SolamanRaji]

Great explanation man :)

[@Taeyang311]

Thanks for the video!

[@BackToBackSWE]

sure

[@dinner4chiahao]

Great video! Thanks!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@pranavparihar4744]

Thanku so much for the explanation :)

[@akankshasharma148]

Great explanation 🙏🙏🌼

[@mallikarjunpidaparthi]

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...

[@MuffinLucas]

Thank you!

[@sahilanand30]

great explanation :)

[@JG-zu6nq]

Good stuff bro.

[@BackToBackSWE]

thanks

[@yaminchoudhury8732]

your a cool guy man thank you for everything

[@BackToBackSWE]

sure!

[@biswajitnayaak]

i wish u were my teacher when i studied software engineering 14 years back

[@AbhishekChauhan-wt1hb]

Quality content ..Thankyou so much

[@BackToBackSWE]

sure

[@Allen-tu9eu]

what a nice intro for dp

[@manojrajasekar6035]

Great one ! Weekend well spent , though :)

[@BackToBackSWE]

nice

[@AngadSingh97]

Hi, is there a way to reframe this problem as an unbounded knapsack and solve it? I tried this, but my code fails to account for the different arrangements (1,1,2 and 1,2,1 and 2,1,1), and simply counts them as a single way.

[@arsyaswanth5]

Dude you're awesome!!!

[@BackToBackSWE]

no you are awesome

[@arsyaswanth5]

@@BackToBackSWE dude i was just seeing your knapsack video and your comment popped up lol!!!

[@suramyasingh1353]

Awesome!!

[@BackToBackSWE]

thanks

[@InnovatetoLife]

Dude ❣️ best explanation

[@BackToBackSWE]

thanks

[@billy-cg1qq]

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)?

[@airysm]

Hey Ben, when do you recommend top down vs bottom up? To me bottom up always seems like the most easy to implement

[@BackToBackSWE]

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.

[@sriramkasu7511]

bro you are too good

[@BackToBackSWE]

thx

[@markfesenk0]

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

[@BackToBackSWE]

I don't remember this video much so can't validate 1, and ok for 2. And ok

[@vinayakmishra9519]

Yeah both the points are true.

[@wl7497]

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?

[@BackToBackSWE]

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.

[@mikasaackerman2694]

8:54 Loved the way you explained recursion lol

[@BackToBackSWE]

what i do

[@DadBodSwagGod]

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

[@BackToBackSWE]

lol nice

[@blasttrash]

revelation? what was that? I am curious...I might have the same revelation too if you let us know. :D

[@BackToBackSWE]

@@blasttrash yo

[@blasttrash]

@@BackToBackSWE yo, whats up. Hope you have a nice weekend. :D

[@BackToBackSWE]

@@blasttrash The weekend just happened

[@mybrightmeteor]

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) .

[@BackToBackSWE]

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).

[@sandeeps7625]

Back To Back SWE this comment too helped a lot , thanks

[@theredorm1961]

Good luck, you get really cool

[@BackToBackSWE]

no u

[@kosamganjoo5694]

why this video has not million hits? he is too good

[@BackToBackSWE]

thanks.

[@woodylucas]

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

[@BackToBackSWE]

sure

[@arunadang2130]

Good one

[@BackToBackSWE]

thanks

[@shehreensaifi846]

you are amazing 😉😉😉

[@vandanpatel3395]

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?

[@BackToBackSWE]

thanks and I dont remember this video much tbh

[@vandanpatel3395]

@@BackToBackSWE No problem, I completely understand. Thanks for your response. Please stay safe!

[@BaishaliGhosh13]

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?

[@BackToBackSWE]

Sounds like that could be solved by restricting the recursion & keeping state on the number of 3's used so far

[@jithinMumbai]

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] ??

[@BackToBackSWE]

"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.

[@sophiehall38]

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]

Canon Rebel T3i

[@sophiehall38]

@@BackToBackSWE Thanks for your reply! Have a nice day!

[@ehsanhosseini5861]

Your videos are excellent. Is Dynamic programming just bottom up approach? When you say bottom up, do you mean Tabulation approach?

[@BackToBackSWE]

thanks, eh not sure

[@chandan3193]

awesome

[@BackToBackSWE]

thx