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

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

[@ayodejiakinola7343]

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

[@BackToBackSWE]

great and thanks

[@queensfinezt]

2:38 golden "Tushar take it away"

[@BackToBackSWE]

my b, old video

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

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

[@qwarlockz8017]

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

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

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

[@danielkashkett7040]

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

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

[@jujubi123-h7k]

Really love the logical flow of the teaching, it helped me! Thank you!

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

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

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

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

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

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

[@venkateshn9884]

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

[@gimmeerkin2131]

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

[@abcdeereijgfhd3215]

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

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

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

[@arxci9402]

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

[@BackToBackSWE]

nice

[@Anonymus1232-x]

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

[@SK-lu7ci]

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

[@BackToBackSWE]

thx

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

[@killeraloo3247]

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

[@talesfromthemidwest]

Finally, an explanation that makes sense.

[@BackToBackSWE]

yo

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

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

[@smithcodes1243]

This is by far the best explanation! Thanks buddy!

[@maximedero4270]

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

[@BackToBackSWE]

sure

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

[@rajatjain7680]

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

[@BackToBackSWE]

nice.

[@amithbk12man]

I really liked the way you explain. Thanks!

[@BackToBackSWE]

sure

[@2tce]

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

[@BackToBackSWE]

nice

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

[@biswajitnayaak]

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

[@shubhamuniyal2417]

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

[@BackToBackSWE]

thx

[@krishnanigalye1173]

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

[@Arnott_me]

Thanks a lot, finally understand how it works!!

[@rchukkapalli1]

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

[@BackToBackSWE]

ok 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

[@kausachan4167]

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*

[@BackToBackSWE]

what lol

[@ginasomara267]

BEST video I have seen on this. TY

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

[@vineethm6930]

Thanks a lot for strengthening my concepts.

[@МарияСкрягина-щ9з]

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

[@BackToBackSWE]

nice - Ben

[@kosamganjoo5694]

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

[@BackToBackSWE]

thanks.

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

[@tejasvigupta07]

Such a great explanation.Instant subscribe.

[@BackToBackSWE]

welcome friend

[@ShreyanGoswami]

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.

[@BackToBackSWE]

yes

[@kuxnal]

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

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

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

[@MacaroonL]

Thank you!! This video was really helpful!

[@BackToBackSWE]

sure

[@SoledadDelSol]

Great explanation for this problem!

[@luisasanchez9267]

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

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

[@wilsonjiang8849]

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

[@BackToBackSWE]

Welcome. I am honored.

[@PomboKad]

You just got a new subscriber. Thank you!

[@BackToBackSWE]

sure

[@techsavvy1457]

Follow-up: Return the steps

[@BackToBackSWE]

!!!!!!!!!!!!!

[@matthewbuchholz7091]

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

[@BackToBackSWE]

lmao something is wrong with me

[@sapunovnik]

Great explanation! Thank you very much!

[@BackToBackSWE]

Of course. Thank you for watching.

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

[@sinat101]

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?

[@helloiam2mas]

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?

[@BackToBackSWE]

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.

[@helloiam2mas]

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

[@bhargavsai2449]

superb!!! superb!!great work

[@BackToBackSWE]

Thank you! Cheers!

[@kalusharma2201]

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

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

[@Allen-tu9eu]

what a nice intro for dp

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

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

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

[@shiladryadak1541]

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

[@BackToBackSWE]

sure!

[@ncpga]

You explained why f(0)=1, I dont see it in other resources. They just told me to remember it without explaining why.

[@4sky]

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.

[@BackToBackSWE]

oops

[@mengruli4103]

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

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

[@akankshasharma148]

Great explanation 🙏🙏🌼

[@yaminchoudhury8732]

your a cool guy man thank you for everything

[@BackToBackSWE]

sure!

[@alvinng1195]

why is f(0) = 1 ? shouldn't it be 0? Since there are only two ways. The first way is to take one step while the second is to take two steps. And since taking 0 steps is not an option, I think f(0) should be 0. What are your thoughts?

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

[@pudisasikar7996]

Great video... But i didn't find any link in description for code.. Is it missed

[@BackToBackSWE]

Hi - the repository is deprecated, we only maintain backtobackswe.com now.

[@pudisasikar7996]

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

[@shoco2]

Great explanation!

[@sriramkasu7511]

bro you are too good

[@BackToBackSWE]

thx

[@yoshi4980]

here is one thing i am confused about. the general solution if you're on the ith step is: i steps = ways to get to i-1 steps + ways to get to i-2 steps but why are you not adding a 1 for each way? meaning why doesn't it look like this: i steps = 1 + ways to get to i-1 steps + 1 + ways to get to i-2 steps my thinking is there is if you're at i-1, you have 1 new way to get to i, and if you're at i-2, you have another new way to get to i-2. thus you add a 1 for each new way, since you still have to perform a 1 or 2 step at i-1 or i-2 respectively for some reason i can't really wrap my head around why you don't add the extra 1s...

[@BackToBackSWE]

What would adding 1 mean in each case? The base cases are the only ones offering a solution, we just defer with the recursive cases because we know to get to a certain step the person must have come from 1 or 2 steps away and each of those respective recursive paths have their own solution, etc. each adding total ways to the current step in an additive manner since it is just combining the possibilities.

[@yoshi4980]

​@@BackToBackSWE i get it now, basically you take all the ways you can get to step i-1, and you take a one step to get to i, but that doesn't add a new way, that's just extending the old paths/sequences that get you to i-1 by a 1 step. same idea for i-2, you take all the ways to get to i-2, and you add a 2 step to get to i, basically extending the old paths/sequences by a 2 step

[@pranavparihar4744]

Thanku so much for the explanation :)

[@AbhishekChauhan-wt1hb]

Quality content ..Thankyou so much

[@BackToBackSWE]

sure

[@arunadang2130]

Good one

[@BackToBackSWE]

thanks

[@Taeyang311]

Thanks for the video!

[@BackToBackSWE]

sure

[@sandeeps7625]

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

[@BackToBackSWE]

thanks

[@free-palestine000]

I know this isn't really the point of the vid, but how did you calculate the exact bound (theta) @11:56?

[@InnovatetoLife]

Dude ❣️ best explanation

[@BackToBackSWE]

thanks

[@mikasaackerman2694]

8:54 Loved the way you explained recursion lol

[@BackToBackSWE]

what i do

[@theredorm1961]

Good luck, you get really cool

[@BackToBackSWE]

no u

[@punstress]

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!

[@BackToBackSWE]

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.

[@SolamanRaji]

Great explanation man :)

[@JG-zu6nq]

Good stuff bro.

[@BackToBackSWE]

thanks