Climbing Stairs - Dynamic Programming - Leetcode 70 - Python

Wow this was a great explanation. I love you ❤

Been learning DP since for ever, only watch your videos can make me wrap my head around, big thanks

@NeetCode, real question, were you able to solve this Climbing Stair problem the first time you came across it?

Funda clear .

why base case is 1? It should be 0. If you at n=5, then there is no way you can take any step, 1 or 2 will over step.

NeetCode says that at level 5 from the options of climbing 1 step or 2 steps there is 1 way to reach level 5... Isn't it 0 tho cause you would get to level 6 or level 7 if you picked those options? Just overall confused about the logic for the base case

this explanation is good, but isn't it more intuitive to start from dp[0] to dp[5], since the numbers will be the same and it's somewhat easier to visualise and understand the problem?

amazing vidoe very helful thanks for it ❤❤

Your explanation is so good brother...so good❤

The code is simple how to find the correct way of approach the problem

Incredibly well explained. Thanks!

The best ever explanation one could ever give. Thanks a lot!

If someone is getting confused on why there is range(n-1) loop instead of range(n-2) loop, here is the answer:

Yes, if there are n stairs, we have n-2 stairs remaining and will have to calculate the value of them . But the place to start is below the 5 stairs. So, we need to calculate the value of 'one' for the base; not the first stair. So, we need to do the loops n-1 times.

When we are at stair 5 , we don't have 1 way to reach the goal, we are already at the goal. But we should put 1 as the value there anyways so that the problem gets solved.
For eg:
if we are at 3 ,
3 ---> 4--->5
\
\
5

Here, whenever we get to 5, we should vallidate the path that bought us there i.e. 1 . 3 to 5 is a valid path , so we give it 1. 4 to 5 is also one valid path , so we should vallidate that, so, putting 1 in place of 5 works. As, it is similar to having a single path from there to the goal.

Incredible incredible explaining. I really understood everything you said.

this was really hard for me

Thank you so much for making this so easy!

The wording was a bit confusing for me, what do you mean if you start at 5, the number of ways to end at 5 is 1?

You are showing a Top Down. Bottom Up will start at 0 and will go to 5

Awesome videos. Been binge watching your channel. Thank you so much..... My only concern was i didn't understand how at staircase 5, there was 1 way to get to 5. When in reality we didn't need to make any move from 5.

Hello guys, newbie to dynamic programming here, I want to ask why it takes one way to start from step 5 to step 5, I thought that'd be zero. anyone to help me out?

So simple, my solution that didnt end up working was this. if n = 6 you have [1,1,1,1,1,1] [2,2,2] and then all combinations of [2,1,1,1,1] and [2,2,1,1]. So you take the combination (5C1,4C2) of the first, plus the combination of the second, plus two in the case that n is even. I feel like my solution works but it just took to much time and this is so much simpler. Computing 45! is not really feasible without doing tricks so thats why this solution was bad.

looks like a reverse fibonachi - given N, walk back the fibonachi way

It is sad to see that code in your samples always has complex one liners assignments but you fail to use the same in main code: [one, two = one + two, one]

The body of the for loop can be simplified to: one, two = one+two, one

Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.

Thank you, Neet. You make our lives easier!

You're smart mate!

Where have you been all my life? Thank you and thank you again. Words have failed. Thank you.

such a good explanation of a fundamental problem

we went through so much headache just to get to these five lines of code HAHAHAH

Why are the number of steps 1 when you are standing at the final stair. In the example you showed that from the 5th stair you would require 1 way to reach to 5th,shouldn't it be 0 ?

sir u said we can solve in bottom up approach but atlast u solved from top itself.

God's work! So much gratitude

Awe inspiring explanation

I had a feeling like I was trolled when I saw these 5 lines of code

amazing

Hmm I know naming is trivial but are you sure the first one is memoization? I think the first one is tabulation (bottom-up) and second one is memoization (top-down). Oh nvm we used different base cases, I used n==-1 and n==0 as base.

You are awesome

My version : def climbStairs(self, n: int) -> int:
s=[0]*n
for i in range(len(s)):
if i==0:
s[0]=1
if i==1:
s[1]=2
if i>1:
s[i]=s[i-1]+s[i-2]
return (s[-1])

Please explain leetcode 980

My brain just exploded after watching the solution! I admit I would never be able to solve it if I had not watched the solution. Who is the first guy figured out this thing? absolutely a genius!

OMG that's so sick

I don’t understand the solutions in code even with these good explanations.