Actually I think the brute force decision tree solution has a time complexity of Phi in the power of n, and not 2 in the power of n, seeing as it grows similarly to Fibonacci series. Great video by the way!
Instead of using a temp-variable you can make use of Python3s tuples (as you already are when you create the variables). one, two = 1,1 for i in range(n-1): one, two = one + two, one return one Behind the scenes it is effectively the same as using a temp variable, but without the ugliness of one! :)
This! Please! Once I've gone through several channels to understand dynamic programming and haven't done it ever since I found your channel. There's simply no need anymore, as not a single channel imo can beat @NeetCode 's way of explaining things! This guy is just phenomenal!
This guy is too very good in explanations www.youtube.com/@nikoo28 , only difference is he doesn't use python but Java instead. for current problem ua-cam.com/video/UUaMrNOvSqg/v-deo.html
12:08 Why is the value for the base case 1? I would have thought it's 0 because if we start at 5, we only have the choice to take 1 step or 2 steps, both of which would lead to out of bounds
It should be zero. This problem has 3 bases cases. 1) dp[n-1] ➜ 0 steps 2) dp[n-2] ➜ 1 step 3) dp[n-3] ➜ 2 steps Now, we can determine the remaining sub-problems. The drawn out approach is explained bottom-up, but the coded solution isn't bottom-up. Here's my bottom-up solution in javascript let currentStep = 0; let previousStep = 1; let totalSteps; // start at the end and move to index 0 for (let i = n-1; i >= 0; i--) { totalSteps = currentStep + previousStep; currentStep = previousStep; previousStep = totalSteps; } return totalSteps;
Bro I don't know how you're so good at simplifying things, but it's incredible. I've watched so many videos on dynamic programming and not one of them has made as much sense as this. I sincerely thank you for all of these videos.
I am preparing for an interview and your videos are simply the best thing I found on the internet. Thank you for your hard work it's helping hundreds of us!
OMG, thank you so much for the clear explanation. I've been struggling to understand the recursion method and why the complexity of Memoization is O(n) for a while. Your decision tree explanation is fantastic and I can finally have a good sleep tonight.
Great Explanation! For others like me, who feel that the number of steps at the 'nth' step (last step) should be 0, the below solution is adapted accordingly: # computing the base case, when we are on the penultimate (n-1) step, or the one before the penultimate (n-2) step penultimate_step, one_before_penultimate = 1, 2 if n == 1: return penultimate_step if n == 2: return one_before_penultimate for i in range(n-2): one_before_penultimate, penultimate_step = penultimate_step + one_before_penultimate, one_before_penultimate return one_before_penultimate
if you consider the base cases of dp[n] = 0, dp[n-1] = 1, dp[n-2] = 2, you can complete the rest using Neet's solution and in that case there is no confusion regarding why dp[n] = 1.
this makes much more sense. I still don't get why do we say there is "1" step from dp[n] if we are already in the last step and there are no steps to do.
@@darioarielgonzalezleegstra1741 because your current position is also the target position (top position) and there is only one way to go there by doing absolutely nothing
For anyone who is confused why the base value is 1. I think we can try to understand better with this code, as we know that dp[2] = 2 and dp[3] = 3, we can just work our way up there. Hope this helps. class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ if n
your example of the loop works and gives 8 with n=5, thanks! But I don't get why code in video for i in range(n-1): temp = one one = 1 + two two = temp with n=5 gives result 3 and not 8? As for me it should be the same 🤔
FYI there is a O(1) solution because there is a closed form expression for Fibonacci numbers. As in, there is an equation for Fn (the nth fibonacci number) that is only a function of n, instead of a function of Fn-1 and Fn-2
Indeed, although I am not sure it is that easy to calculate the nth fibonacci number in constant time, because exponentiation takes O(logn). It is also worth mentioning that one would have to use the known matrix exponentiation algorithm for fibonacci numbers, to avoid precision problems that arise from exponentiation of irrational numbers. Either way, though, it is indeed true that this observation leads to a faster solution, nice.
Great video as always !! here is the recursion based DP approach in Python if anyone requires. class Solution: def climbStairs(self, n: int) -> int:
# dfs appraoch def helper(n, index, memo={}): # base case if index > n: return 0 if index == n: memo[index] = 1 return 1 if index in memo: return memo[index] # recursion case memo[index] = (helper(n, index+1, memo) + helper(n, index+2, memo)) return memo[index] return helper(n, 0)
Your explanations are really helpful! and efficient I don't know why this channel or video is very less subscribers/views , most underrated. YOU DESERVE BETTER ! keep it up
Beautifully explained. You really took the time to first establish what the problem was asking. I really appreciate you breaking down this problem conceptually and then proceeding to highlight how and why dynamic programming was the way to approach this problem through the use of DFS, recursion and memoization. Instead of just providing the 5 line solution after a few minutes of going through this problem, you took the time to provide an in-depth explanation and help cement the PROCESS of arriving at solution in my mind. So glad I subscribed to your channel and thank you very much!
Great video! I still will need to rewatch this a few times I think, but eventually this will make sense. I get the memoization solution at least. For anyone looking for the memoization code, I copied this from the solution section but this will save you a few clicks: class Solution: def climbStairs(self, n: int) -> int: memo = {} memo[1] = 1 memo[2] = 2 def climb(n): if n in memo: return memo[n] else: memo[n] = climb(n-1) + climb(n-2) return memo[n] return climb(n)
I have watched this solution so many times and every time it amazes me the same. Love how you started with a brute force solution, made it better and finally made it waaaay better and simple. Helps to build a "thought process" and see the many ways of solving the same problem 🙏👏❤🔥
@Mohammed Why is taking "no step" (= 0 steps) an option here given the constraints of the problem (i.e. taking 1 or 2 steps)? When we looked at the earlier visualizations how to reach "n", we stopped once we actually reached "n" by previously taking either 1 or 2 steps. We didn't get at stair "n" and then at "n" said: "Ok there's is one last option which basically is taking no step, so we also have to count this last option". During bottom-up at 4 we also say there is only 1 way to get to 5: take 1 step. We don't consider the case "take 0 steps followed by 1 step".
@@andreipoehlmann913 I find it easier to reason about this way as well. - The number of ways to reach stair `n` starting from stair `n` is 0. - The number of ways to reach stair `n` starting from stair `n - 1` is 1. - The number of ways to reach stair `n` starting from stair `n - 2` is 2. And so forth. Granted, my code is icky compared to Neet's. Neet's code effectively _seeds_ the value of stair `n - 2`. ``` class Solution: def climbStairs(self, n: int) -> int: n_minus_one = 1 n_minus_two = 2 if n == 1: return n_minus_one if n == 2: return n_minus_two # i begins at n - 3 i_plus_one, i_plus_two = n_minus_two, n_minus_one i = i_plus_one + i_plus_two for _ in range(n - 4, -1, -1): i_plus_one, i_plus_two = i, i_plus_one i = i_plus_one + i_plus_two return i ```
def climbStairs(n): # if you are at n-2 a = 2 # if you are at n-1 b = 1 if n == 1: return 1 if n == 2: return 2 for _ in range(n-2): a, b = a+b, a return a
It looks like this covers the edge case of being on the last step. I agree it doesn't make sense. You could do it by covering the edge cases of n = 1 and n = 2 then starting with the nth-1 step. There's a comment below that shows this, by @sankalp.
Looking at it for me this was an extremely complicated way to describe Fibonacci sequence. Here how I think about it (it is pretty much the same, just a different perspective, might be easier for some people to understand it. Thinking backwards what is the last "move" we did. We either Jumped 1 step or we jumped two steps. This means that if f(n) is the function that calculates how many steps it takes to get to the n-th step f(n) = f(n-1) + f(n-2). Then if you continue the logic you can see how this is the same as your decision tree diagram: f(n) = f(n-1) + f(n-2) = (f(n-2) + f(n-3)) + f(n-2) and so on. We can easily recognize this is Fibonacci sequence, we can even see it with some examples: To get to 1 step (f(1)) you only have 1 way. 2 steps (f(2)) - 2 ways (2 or 1+1) Then to get to three f(3) we just sum the previous two f(3)= f(2)+f(1) = 2+1 = 3, f(4)=f(3)+f(2) = 3+2=5, f(5)=f(4)+f(3)=5+3=8 and so on. Then depending on how we want to solve it programmatically we can choose an approach.
Ok, hats off to you. The problem can be 'easy', but with your explanation of Memoization and bottom-up approach, you make this a 'must understand' problem. Thank you very much for all your efforts to explain it to us.
Theres a reason why this video has so many views! its so good. I do have one question. I am confused why in the DP array why is 5 equal to 1? I understand its the base case but you also said there's one way to get to 5 from 5 but shouldn't it be zero? (12:15)
To better visualise it, take a top down approach. For example, If it's 3, you have 2 decisions to make at every step to reach the bottom stair. Either you could take 1 step or 2 steps. So, the decision tree will look like this. The left edge represents 1 step and the right edge represents 2 steps. 3 / \ 2 1 / \ / \ 1 0 0 -1 / \ 0 -1 So, when you reach 0 return 1 and when you n < 0 return 0 Also, if you notice it is like the Fibonacci sequence 1 1 2 3 5 8 13.... And then the memoisation is easy t reduce the time complexity
Nice way to look at problems. I started using some kind of combinatorics and modular arithmetic, and I was like "why is this a Fibonacci sequence?" And then I thought that it kinda made sense as the case n+1 was something like the solution for n plus the solutions to go from the n step to n+1 (sort of, I took a little time to better catch the pattern). But looking at it as a top to bottom problem made waaaay easier. And I'm not really used to the notions of storing results and looking at solutions as an algorithm instead of an equation really help me ace my future interviews. Thanks for the video. You just earned a subscriber :)
The beauty of this solution is that the question being asked is how many different routes, not what are ALL the different routes, hence the optimisation shown here. Fantastic work.
Wow, awesome. When I see how Neetcode solve a problem, I feel it is really important to figure out a way to solve a problem. First try, I used bruceforce, and I watched this video 30% and I solved a problem using DP but still used recursive calls, I finished watching the explanation and it was A-ha moment and I solved the problem using an array, and I thought I did it well then I saw the code he doesn't even need an array. Awesome.....awesome...
If you looked a bit closer at it you would see that the numbers you get are the fibonnaci numbers. There is a closed form way to calculate any, without calculating previous terms. That uses the golden ratio, and is relatively expensive for small numbers, but dominates for large numbers
Here is the Top Down approach for anybody curious class Solution: def climbStairs(self, n: int) -> int: memo = {} def climb(m): if m in memo: return memo[m] if m == n: return 1 if m > n: return 0 memo[m] = climb(m+1) + climb(m+2) return memo[m] return climb(0)
I found it easier just looking at the three base cases and then deriving dp array/slice; one stair, two stair or three stairs. // 1 stair = 1 way // 2 stairs = 2 ways // 3 stairs = (take 1 step + sum of 2 stairs) + take 2 steps + sum of 1 stairs) // 3 stairs = (take 1 step + sum of 3-1 stairs) + take 2 steps + sum of 3-2 stairs // n stairs = (take 1 step + sum of n-1 stairs)+ take 2 steps + sum of n-2 stairs // n stairs = n-1 + n-2 //golang // o(n) space and time func climbStairs(n int) int { if n == 1 { return 1 } if n == 2 { return 2 }
dp := make([]int, n) dp[0] = 1 dp[1] = 2
for i := 2; i < n; i++ { dp[i] = dp[i-1] + dp[i-2] } return two } From here, you can optimize space to be O(1) instead of O(n) by realizing that you only need two-three variables to store dp[i-1] and dp[i-2], and d[i] //O(1) space and O(n) time func climbStairs(n int) int { if n == 1 { return 1 } if n == 2 { return 2 }
previousStairSum, currentStairSum:= 1, 2
for i := 2; i < n; i++ { previousStairSum, currentStairSum= currentStairSum, previousStairSum + currentStairSum } return currentStairSum }
nit: you can use tuple packing and unpacking for simultaneous state updates. Example: def fibonacci(n): x, y = 0, 1 for i in range(n): print x x, y = y, x+y This removes the need for a temporary variable. Just a nit, thank you for all that you do.
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.
This problem has a better solution than O(n). You can conceptualize it as a fibonaccis suite of numbers (clearly visible at 15:27). the solution becomes: steps(n) = fib(n+1) and computing fib numbers is O(log(n)). cheers :)
Having 1 way to reach 5, starting from 5, doesn't make any sense to me. Since we can only move 1 or 2 steps, there should be no ways at all to land on the last step, as you would need to move exactly zero steps. And that's no allowed because the rules explicitly say "Each time you can either clime 1 or 2 steps" if we start at 5, and check how many ways we can reach 5 using the tree system: 5+1 = 6 [invalid = 0] 5+2 = 6 [invalid = 0] add up all branch ends: 0 + 0 = 0 therefore there are 0 ways to reach 5, from 5.
That's exactly what I was thinking. But I think the phrasing is slightly strange in this problem. I've been looking at it for a min and realized it says it takes n steps to REACH the top. SO if we're at the nth (last) step, then we only need to take ONE more step to have reached the top. The same could be said for n-1th step; we can just jump TWO more steps and be done, so by default, there's 1 way to move from n to the end and 1 way to move from n-1 to the end.
this one was hard for me because I could easily do UNIQUE combinations, but thats not what the question asked for. It counts 122 along with 212 and 221 (for 5 steps) as valid combinations, even though they arent unique.
I actually figured out a way to do it w/combinations. All you have to do is divide the number of steps you took, N, by the product of the factorial of each repeated number. So if you want to climb 7 steps, if you only take a 2-step once, it would look like 111112. Since 1 repeats 5 times and 2 only once, you get 6!/(5!*1!). Do this for the amount of times that you can take 2 out of 7 evenly and add them together. So 7/2 = 3.5 you would repeat that 3 times adding adding another two and removing the ones respectively.
I couldnt stop thinking who came up with this algorithm. You go from a long manner of counting by ones and twos, to creating a decision tree, to finding patterns and see how can you simplify the code, to ultimately realizing that counting backwards can simplify the counting, to ultimately recognizing the solution is simply the fibornacci series of numbers. TOo easy, becuase some genius paved the way... amazing
lol, i am currently completing the spreadsheet and I was surprised u didn't have a video of this problem so i google it and here it is. thanks bro really nice content
This is one of those questions where the solution is so simple when you look at it when you look at the recurrence, but then you're in disbelief so you try to enumerate all the combinations
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.
The question is, how many different ways can you reach the top from where you're standing? The answer is simply one - you're already there! You don't need to do anything or take any extra steps. But I understand it's confusing.
@@_SoundByte_his doubt makes sense. There's one way to go from 4 to 5 and there's one way again to go from 5 to 5. How is this making sense. From the surface it is looking like the value 1 was assumed for the base step.
@@shawcking2472 Agreed. This explanation doesn't suffice me either. For me it makes more sense for the base case to be staircase 3 and 4: How many steps from 3 to 5? 2 How many steps from 4 to 5? 1. Then: def climbStairs(self, n: int) -> int: if n
sorry I don't seem to get why the base case of 5 needing one step to get there? I thought it would be 0 since we are already at the place we want to get to?
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.
solution for fast count given 'n', number of stairs in python. No DP needed: from math import comb n = 6; sum([comb(n-r, r) for r in range(n//2+1 if n%2 == 0 else (n-1)//2+1)])
def climbStairs(self, n: int) -> int: penultimate, ultimate = 0, 1 for i in range(n): penultimate, ultimate = ultimate, penultimate + ultimate return ultimate This also works as a solution. 1. We take n steps via range(n) 2. We don't need a temp var, since we shift over the penultimate value and calculate the ultimate value simultaneously. 3. This makes more sense intuitively than starting at 'base case = 1' when starting from the last step and working backwards. Instead, we start with 0 paths to reach the 0th step (penultimate) and 1 path to reach the 1st step (ultimate), then build up from there. After n loops, our last (ultimate) step can be returned directly.
Why are the base cases both 1? In the n=5 drawing solution (at 12:12), there are 0 ways to get to step 5 if you are already on step 5? Considering there are no options for taking 0 steps?
First of all, thanks once again for comprehensive and well done explanation about this problem 🥇 ! Second, I had difficulties to comprehend the movement into the solution code it was just too fast for me. In addition I didn't understand why dp[n] == 1 and not 0 - since logically it's the target number, so we won't need to do more steps... As a suggestion, in case others will struggle like me, I think it's better to start with the recursive solution and to see how it's similar to Fibonacci solution. Then, trying to print solutions for n= 0, 1, 2, 3, 4, 5 and to see the pattern -> this explain why dp[n] == 1 - it's because we wrote the function to return 1 in case number == 0 and when we translate this to a loop, we want to init the first value into 1. Second value will also be 1 - run the recursive function (with debug prints) and see why. After you see the Fib pattern, all you need to do is to implement a fib loop to return the number as shown in the video.
Bumping the other guy's question. Why is it that 5 results in value of 1 in the DP array? if you take 1 step from 5 or 2 steps from 5 you'll be out of bounds either way; why does it not follow the same pattern as calculating the steps from 4 to 5?
Just one question, at the end when you create the third variable, wouldnt be better to say two = one - two? if the goal of not using an array was to reduce memory cost that would fit
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
@NeetCode can you do binary tree cameras?
Actually I think the brute force decision tree solution has a time complexity of Phi in the power of n, and not 2 in the power of n, seeing as it grows similarly to Fibonacci series.
Great video by the way!
why have a temp variable when you could write:
two = one
one = one + two ?
Edit: Oh it's because it would change the one plus two line duh
Instead of using a temp-variable you can make use of Python3s tuples (as you already are when you create the variables).
one, two = 1,1
for i in range(n-1):
one, two = one + two, one
return one
Behind the scenes it is effectively the same as using a temp variable, but without the ugliness of one! :)
Using base condition, when at 5(n=5 problem), why there is 1 way to reach 5, as you already stand there, why Not Zero(0) ?? Can anyone tell ?
this is probably the hardest 'easy' tag question I've come across
if I didnt recognize the fibbonacci i would have been screwed lol
literally, every single solution I saw besides fibbonacci I just do not understand lol@@warguy6474
@@warguy6474i didn't know the fibbonacci before this video
@@trh786fed I think if you take an intro computer science course in highschool or college they usually address it once but that's pretty much it
Wait until you checkout 1002 : Find Common Characters
Thank u very much!!! Because of your tutorials, I got interest and thinking visually for solving DSA problems.. Now I have a job in MNC too..
how do u visualise dsa ??
@@demonslayer4607by closing his eyes.
@@demonslayer4607decision tree ?
can we connect?
@@demonslayer4607 i suppose, this entire channel visualizing DSA
your videos should be in Leetcode's editorial solutions. Clear, concise, and so easy to understand.
This! Please! Once I've gone through several channels to understand dynamic programming and haven't done it ever since I found your channel. There's simply no need anymore, as not a single channel imo can beat @NeetCode 's way of explaining things! This guy is just phenomenal!
He's a genius! His videos are such a blessing!
Definitely. Leetcode should pay him
This guy is too very good in explanations www.youtube.com/@nikoo28 , only difference is he doesn't use python but Java instead.
for current problem
ua-cam.com/video/UUaMrNOvSqg/v-deo.html
12:08
Why is the value for the base case 1? I would have thought it's 0 because if we start at 5, we only have the choice to take 1 step or 2 steps, both of which would lead to out of bounds
I too have same question, it should be zero
Same question, Any leads ? Thanks
Agreed. That doesn't make sense.
same question here, has anyone found out?
It should be zero. This problem has 3 bases cases.
1) dp[n-1] ➜ 0 steps
2) dp[n-2] ➜ 1 step
3) dp[n-3] ➜ 2 steps
Now, we can determine the remaining sub-problems. The drawn out approach is explained bottom-up, but the coded solution isn't bottom-up. Here's my bottom-up solution in javascript
let currentStep = 0;
let previousStep = 1;
let totalSteps;
// start at the end and move to index 0
for (let i = n-1; i >= 0; i--) {
totalSteps = currentStep + previousStep;
currentStep = previousStep;
previousStep = totalSteps;
}
return totalSteps;
17:40
" ah Yes.. makes sense so far"
17:50
"WAIT ITS OVER?!"
The most underrated channel on UA-cam!!
💯
Thanks
Hey Meg, thank you so much! I really appreciate it 😊
Bro I don't know how you're so good at simplifying things, but it's incredible. I've watched so many videos on dynamic programming and not one of them has made as much sense as this. I sincerely thank you for all of these videos.
this is also Fibonacci
I am preparing for an interview and your videos are simply the best thing I found on the internet.
Thank you for your hard work it's helping hundreds of us!
instead of storing a temp variable, you can do this in python3+:
one, two = one + two, one
it also uses temp value in the background.
Or use: "one = one + two" and then "two = one - two" to do the same thing without an implicit temp variable.
@@farmanguliyev yes, but the code is cleaner
OMG, thank you so much for the clear explanation. I've been struggling to understand the recursion method and why the complexity of Memoization is O(n) for a while. Your decision tree explanation is fantastic and I can finally have a good sleep tonight.
Great Explanation!
For others like me, who feel that the number of steps at the 'nth' step (last step) should be 0, the below solution is adapted accordingly:
# computing the base case, when we are on the penultimate (n-1) step, or the one before the penultimate (n-2) step
penultimate_step, one_before_penultimate = 1, 2
if n == 1: return penultimate_step
if n == 2: return one_before_penultimate
for i in range(n-2):
one_before_penultimate, penultimate_step = penultimate_step + one_before_penultimate, one_before_penultimate
return one_before_penultimate
if you consider the base cases of dp[n] = 0, dp[n-1] = 1, dp[n-2] = 2, you can complete the rest using Neet's solution and in that case there is no confusion regarding why dp[n] = 1.
I was having the same doubt, Thanks
this makes much more sense. I still don't get why do we say there is "1" step from dp[n] if we are already in the last step and there are no steps to do.
@@darioarielgonzalezleegstra1741 because your current position is also the target position (top position) and there is only one way to go there by doing absolutely nothing
@@sapientia230 but then it means 0 ways, because it doesn't make any sense you have 1 way to reach 5 from 4 but you also have 1 way to reach5 from 5
For anyone who is confused why the base value is 1. I think we can try to understand better with this code, as we know that
dp[2] = 2 and dp[3] = 3, we can just work our way up there. Hope this helps.
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n
Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.
Thank you! Great explanation. A slightly more compact code:
one, two = 1, 1
for i in range(n-1):
one, two = one + two, one
return one
you don't even need "i" you can replace it with "_"
your example of the loop works and gives 8 with n=5, thanks! But I don't get why code in video
for i in range(n-1):
temp = one
one = 1 + two
two = temp
with n=5 gives result 3 and not 8? As for me it should be the same 🤔
FYI there is a O(1) solution because there is a closed form expression for Fibonacci numbers. As in, there is an equation for Fn (the nth fibonacci number) that is only a function of n, instead of a function of Fn-1 and Fn-2
Indeed, although I am not sure it is that easy to calculate the nth fibonacci number in constant time, because exponentiation takes O(logn). It is also worth mentioning that one would have to use the known matrix exponentiation algorithm for fibonacci numbers, to avoid precision problems that arise from exponentiation of irrational numbers. Either way, though, it is indeed true that this observation leads to a faster solution, nice.
@@spirosgalanopoulos2560 When you say exponentiation, do you mean calculation of √5 and of the golden ratio constants?
@@sb_dunk I was referring to ((1+sqrt(5))/2)^n.
@@spirosgalanopoulos2560 Oh yes, of course!
Yes exactly. In fact the original problem as stated, before any analysis is done, smacks of a problem that probably has a closed solution.
Great video as always !!
here is the recursion based DP approach in Python if anyone requires.
class Solution:
def climbStairs(self, n: int) -> int:
# dfs appraoch
def helper(n, index, memo={}):
# base case
if index > n:
return 0
if index == n:
memo[index] = 1
return 1
if index in memo:
return memo[index]
# recursion case
memo[index] = (helper(n, index+1, memo) + helper(n, index+2, memo))
return memo[index]
return helper(n, 0)
Your explanations are so good, I'm so grateful that I get to watch your videos.
> always start with a brute-force recursive solution- the best way to start solving any DP problem, *then* apply memoization/tabulation techniques
Your explanations are really helpful! and efficient I don't know why this channel or video is very less subscribers/views , most underrated. YOU DESERVE BETTER ! keep it up
Beautifully explained. You really took the time to first establish what the problem was asking. I really appreciate you breaking down this problem conceptually and then proceeding to highlight how and why dynamic programming was the way to approach this problem through the use of DFS, recursion and memoization. Instead of just providing the 5 line solution after a few minutes of going through this problem, you took the time to provide an in-depth explanation and help cement the PROCESS of arriving at solution in my mind. So glad I subscribed to your channel and thank you very much!
Great video! I still will need to rewatch this a few times I think, but eventually this will make sense.
I get the memoization solution at least.
For anyone looking for the memoization code, I copied this from the solution section but this will save you a few clicks:
class Solution:
def climbStairs(self, n: int) -> int:
memo = {}
memo[1] = 1
memo[2] = 2
def climb(n):
if n in memo:
return memo[n]
else:
memo[n] = climb(n-1) + climb(n-2)
return memo[n]
return climb(n)
I have watched this solution so many times and every time it amazes me the same. Love how you started with a brute force solution, made it better and finally made it waaaay better and simple. Helps to build a "thought process" and see the many ways of solving the same problem 🙏👏❤🔥
During Bottom up, why did you take "" n = 5 "" as "" 1 "" because shouldn't no.of ways to reach "" n = 5 "" from "" n = 5 "" be ""0"" ?
@Mohammed Why is taking "no step" (= 0 steps) an option here given the constraints of the problem (i.e. taking 1 or 2 steps)? When we looked at the earlier visualizations how to reach "n", we stopped once we actually reached "n" by previously taking either 1 or 2 steps. We didn't get at stair "n" and then at "n" said: "Ok there's is one last option which basically is taking no step, so we also have to count this last option". During bottom-up at 4 we also say there is only 1 way to get to 5: take 1 step. We don't consider the case "take 0 steps followed by 1 step".
@@andreipoehlmann913 I find it easier to reason about this way as well.
- The number of ways to reach stair `n` starting from stair `n` is 0.
- The number of ways to reach stair `n` starting from stair `n - 1` is 1.
- The number of ways to reach stair `n` starting from stair `n - 2` is 2.
And so forth. Granted, my code is icky compared to Neet's. Neet's code effectively _seeds_ the value of stair `n - 2`.
```
class Solution:
def climbStairs(self, n: int) -> int:
n_minus_one = 1
n_minus_two = 2
if n == 1: return n_minus_one
if n == 2: return n_minus_two
# i begins at n - 3
i_plus_one, i_plus_two = n_minus_two, n_minus_one
i = i_plus_one + i_plus_two
for _ in range(n - 4, -1, -1):
i_plus_one, i_plus_two = i, i_plus_one
i = i_plus_one + i_plus_two
return i
```
def climbStairs(n):
# if you are at n-2
a = 2
# if you are at n-1
b = 1
if n == 1: return 1
if n == 2: return 2
for _ in range(n-2):
a, b = a+b, a
return a
Also curious to know the answer…
It looks like this covers the edge case of being on the last step. I agree it doesn't make sense. You could do it by covering the edge cases of n = 1 and n = 2 then starting with the nth-1 step.
There's a comment below that shows this, by @sankalp.
'just five lines' of but neat code. I appreciate your tutorials for easy-to-understand explanations
I have watched it from many other UA-camrs, no one even comes near you...
Crisp and clear... Very good explanation
you explain like I'm a dumbass and this is why I like it
two years later, we are still learning! Brilliant. Thank you!
I love that you always start with a brute force solution, making the dp solution really natual in contrast.
Looking at it for me this was an extremely complicated way to describe Fibonacci sequence. Here how I think about it (it is pretty much the same, just a different perspective, might be easier for some people to understand it.
Thinking backwards what is the last "move" we did. We either Jumped 1 step or we jumped two steps. This means that if f(n) is the function that calculates how many steps it takes to get to the n-th step f(n) = f(n-1) + f(n-2). Then if you continue the logic you can see how this is the same as your decision tree diagram: f(n) = f(n-1) + f(n-2) = (f(n-2) + f(n-3)) + f(n-2) and so on.
We can easily recognize this is Fibonacci sequence, we can even see it with some examples: To get to 1 step (f(1)) you only have 1 way. 2 steps (f(2)) - 2 ways (2 or 1+1) Then to get to three f(3) we just sum the previous two f(3)= f(2)+f(1) = 2+1 = 3,
f(4)=f(3)+f(2) = 3+2=5, f(5)=f(4)+f(3)=5+3=8 and so on.
Then depending on how we want to solve it programmatically we can choose an approach.
Ok, hats off to you. The problem can be 'easy', but with your explanation of Memoization and bottom-up approach, you make this a 'must understand' problem. Thank you very much for all your efforts to explain it to us.
This solution is very tied to the 1 and 2 steps. I would expect a more generic solution with different step sizes i.e. n=10, steps=1,2,5
Theres a reason why this video has so many views! its so good. I do have one question. I am confused why in the DP array why is 5 equal to 1? I understand its the base case but you also said there's one way to get to 5 from 5 but shouldn't it be zero? (12:15)
To better visualise it, take a top down approach. For example,
If it's 3, you have 2 decisions to make at every step to reach the bottom stair. Either you could take 1 step or 2 steps. So, the decision tree will look like this. The left edge represents 1 step and the right edge represents 2 steps.
3
/ \
2 1
/ \ / \
1 0 0 -1
/ \
0 -1
So, when you reach 0 return 1 and when you n < 0 return 0
Also, if you notice it is like the Fibonacci sequence 1 1 2 3 5 8 13....
And then the memoisation is easy t reduce the time complexity
12:12 Why the value is 1 instead of 0? We are already at the destination and why do we need one more step to get there?
Thank you so much for taking the time to explain this. It makes a lot more sense now.
I'm getting OCD when I see you solved this without calling the orignal function back!.. Great work. Thank You.
Where have you been all my life? Thank you and thank you again. Words have failed. Thank you.
Nice way to look at problems.
I started using some kind of combinatorics and modular arithmetic, and I was like "why is this a Fibonacci sequence?" And then I thought that it kinda made sense as the case n+1 was something like the solution for n plus the solutions to go from the n step to n+1 (sort of, I took a little time to better catch the pattern).
But looking at it as a top to bottom problem made waaaay easier. And I'm not really used to the notions of storing results and looking at solutions as an algorithm instead of an equation really help me ace my future interviews. Thanks for the video. You just earned a subscriber :)
The beauty of this solution is that the question being asked is how many different routes, not what are ALL the different routes, hence the optimisation shown here. Fantastic work.
The decision tree makes it so clear. Absolutely brilliant my friend!
Neetcode will go down as a legend in programming circles.
Wow, awesome. When I see how Neetcode solve a problem, I feel it is really important to figure out a way to solve a problem. First try, I used bruceforce, and I watched this video 30% and I solved a problem using DP but still used recursive calls, I finished watching the explanation and it was A-ha moment and I solved the problem using an array, and I thought I did it well then I saw the code he doesn't even need an array. Awesome.....awesome...
Thanks for the videos. Just wanted to remind you that you don't need temp variables if you do tuple assignment (ie one, two = one + two, one)
I wait for this in video, bcause its very pythonic way
Been learning DP since for ever, only watch your videos can make me wrap my head around, big thanks
first time listening about dynamic programming completely understood.
jesus, that array in the end was really the top anime plot twist of all time. fantastic explanation, my man, that's a sub right there
If you looked a bit closer at it you would see that the numbers you get are the fibonnaci numbers. There is a closed form way to calculate any, without calculating previous terms. That uses the golden ratio, and is relatively expensive for small numbers, but dominates for large numbers
Coming from an industry that relies heavily on number series, this was my first intuition as well
Here is the Top Down approach for anybody curious
class Solution:
def climbStairs(self, n: int) -> int:
memo = {}
def climb(m):
if m in memo: return memo[m]
if m == n:
return 1
if m > n:
return 0
memo[m] = climb(m+1) + climb(m+2)
return memo[m]
return climb(0)
I got this memoaization approach by my own but this bottom up is fantastic.
You are genious!
I found it easier just looking at the three base cases and then deriving dp array/slice; one stair, two stair or three stairs.
// 1 stair = 1 way
// 2 stairs = 2 ways
// 3 stairs = (take 1 step + sum of 2 stairs) + take 2 steps + sum of 1 stairs)
// 3 stairs = (take 1 step + sum of 3-1 stairs) + take 2 steps + sum of 3-2 stairs
// n stairs = (take 1 step + sum of n-1 stairs)+ take 2 steps + sum of n-2 stairs
// n stairs = n-1 + n-2
//golang
// o(n) space and time
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
dp := make([]int, n)
dp[0] = 1
dp[1] = 2
for i := 2; i < n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return two
}
From here, you can optimize space to be O(1) instead of O(n) by realizing that you only need two-three variables to store dp[i-1] and dp[i-2], and d[i]
//O(1) space and O(n) time
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
previousStairSum, currentStairSum:= 1, 2
for i := 2; i < n; i++ {
previousStairSum, currentStairSum= currentStairSum, previousStairSum + currentStairSum
}
return currentStairSum
}
same as my idea, I think it is easier to come up with this solution
man, you just made it eazzzz. Great explanation btw
nit: you can use tuple packing and unpacking for simultaneous state updates.
Example:
def fibonacci(n):
x, y = 0, 1
for i in range(n):
print x
x, y = y, x+y
This removes the need for a temporary variable. Just a nit, thank you for all that you do.
Good point!
Awesome solution, you doont need a temp var, use python power:
one, two = 1, 1
for _ in range(n - 1):
one, two = one + two, one
Both, the way you explain and the animations you provide, are truly awesome!
12:57 how we will be having 1 step when we are on step 5 to reach the solution, can u explain that part alone ?
I love how intense the liner gets
You have a talent of explaining hard concepts easily. Thank you.
My interest in programming after watching this video 📈📈
Amazing explanation. Loved it
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.
This is the best explanation I have seen. Thanks
This problem has a better solution than O(n). You can conceptualize it as a fibonaccis suite of numbers (clearly visible at 15:27).
the solution becomes:
steps(n) = fib(n+1)
and computing fib numbers is O(log(n)).
cheers :)
Having 1 way to reach 5, starting from 5, doesn't make any sense to me.
Since we can only move 1 or 2 steps, there should be no ways at all to land on the last step, as you would need to move exactly zero steps. And that's no allowed because the rules explicitly say "Each time you can either clime 1 or 2 steps"
if we start at 5, and check how many ways we can reach 5 using the tree system:
5+1 = 6 [invalid = 0]
5+2 = 6 [invalid = 0]
add up all branch ends:
0 + 0 = 0
therefore there are 0 ways to reach 5, from 5.
That's exactly what I was thinking. But I think the phrasing is slightly strange in this problem. I've been looking at it for a min and realized it says it takes n steps to REACH the top. SO if we're at the nth (last) step, then we only need to take ONE more step to have reached the top. The same could be said for n-1th step; we can just jump TWO more steps and be done, so by default, there's 1 way to move from n to the end and 1 way to move from n-1 to the end.
I cannot express how clever you are. Genius.
One of the best explanations I have ever heard.
this one was hard for me because I could easily do UNIQUE combinations, but thats not what the question asked for. It counts 122 along with 212 and 221 (for 5 steps) as valid combinations, even though they arent unique.
I actually figured out a way to do it w/combinations. All you have to do is divide the number of steps you took, N, by the product of the factorial of each repeated number. So if you want to climb 7 steps, if you only take a 2-step once, it would look like 111112. Since 1 repeats 5 times and 2 only once, you get 6!/(5!*1!). Do this for the amount of times that you can take 2 out of 7 evenly and add them together. So 7/2 = 3.5 you would repeat that 3 times adding adding another two and removing the ones respectively.
Very nice explanation, I understood the whole concept of Dynamic Programming in one video. Thank you!
I couldnt stop thinking who came up with this algorithm. You go from a long manner of counting by ones and twos, to creating a decision tree, to finding patterns and see how can you simplify the code, to ultimately realizing that counting backwards can simplify the counting, to ultimately recognizing the solution is simply the fibornacci series of numbers. TOo easy, becuase some genius paved the way... amazing
whilst storing the initial value of "one" totally works, setting two = one - two does not require the temporary variable.
to me, this is literally mind blowing, your explanation is perfect. thank you
lol, i am currently completing the spreadsheet and I was surprised u didn't have a video of this problem so i google it and here it is. thanks bro really nice content
Which spread sheet??
@@rakeshakkannagari7559 this one docs.google.com/spreadsheets/...
Wow...🤯 Thank you for the amazing explanation and experience, feels like Im back in college. Now im going to sit down for an hour and process it all
The ending was the biggest plot twist of my life. Thought it was going to be super complex. It's just 5 lines of cute code 🤣🤣🤣🤣
This is one of those questions where the solution is so simple when you look at it when you look at the recurrence, but then you're in disbelief so you try to enumerate all the combinations
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.
The question is, how many different ways can you reach the top from where you're standing? The answer is simply one - you're already there! You don't need to do anything or take any extra steps. But I understand it's confusing.
@@_SoundByte_his doubt makes sense. There's one way to go from 4 to 5 and there's one way again to go from 5 to 5. How is this making sense.
From the surface it is looking like the value 1 was assumed for the base step.
@@shawcking2472 Agreed. This explanation doesn't suffice me either.
For me it makes more sense for the base case to be staircase 3 and 4:
How many steps from 3 to 5? 2
How many steps from 4 to 5? 1.
Then:
def climbStairs(self, n: int) -> int:
if n
HOW CAN ONE BE THIS GENIUS OMGGGGGG WONDERFUL APPROACH
sorry I don't seem to get why the base case of 5 needing one step to get there? I thought it would be 0 since we are already at the place we want to get to?
13:54 don't understand reasons why should sum previous 2 stairs step combinations. Are there any rule or what ?
why in the dp array the 5th step doesn't have a zero, but has one?
this is a very interesting solution . it makes lot of sense now how programming make life simple
this is a really good explanation!
Thanks!
Nothing easy about this 😅 except for the miraculous explanations of this channel as always! 🙏
The best ever explanation one could ever give. Thanks a lot!
Thank you, I watched another vídeos about the problem and it's the first explanation I saw about decision tree. Made me think different
Wow this was a great explanation. I love you ❤
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.
solution for fast count given 'n', number of stairs in python. No DP needed:
from math import comb
n = 6; sum([comb(n-r, r) for r in range(n//2+1 if n%2 == 0 else (n-1)//2+1)])
A much better and clearer explanation of DP than my algorithm course…
def climbStairs(self, n: int) -> int:
penultimate, ultimate = 0, 1
for i in range(n):
penultimate, ultimate = ultimate, penultimate + ultimate
return ultimate
This also works as a solution.
1. We take n steps via range(n)
2. We don't need a temp var, since we shift over the penultimate value and calculate the ultimate value simultaneously.
3. This makes more sense intuitively than starting at 'base case = 1' when starting from the last step and working backwards. Instead, we start with 0 paths to reach the 0th step (penultimate) and 1 path to reach the 1st step (ultimate), then build up from there. After n loops, our last (ultimate) step can be returned directly.
Why are the base cases both 1? In the n=5 drawing solution (at 12:12), there are 0 ways to get to step 5 if you are already on step 5? Considering there are no options for taking 0 steps?
Steps needed from 5 to reach 5 should be zero right? 12:20
17:54: "We went through so much headache just to get to these 5 lines of code"
Software Engineering in a nutshell
This is crazy simple, man. Just love it 100%
Your Decision Tree explained memoisation succinctly. Thanks !!!
First of all, thanks once again for comprehensive and well done explanation about this problem 🥇 !
Second, I had difficulties to comprehend the movement into the solution code it was just too fast for me.
In addition I didn't understand why dp[n] == 1 and not 0 - since logically it's the target number, so we won't need to do more steps...
As a suggestion, in case others will struggle like me, I think it's better to start with the recursive solution and to see how it's similar to Fibonacci solution.
Then, trying to print solutions for n= 0, 1, 2, 3, 4, 5 and to see the pattern -> this explain why dp[n] == 1 - it's because we wrote the function to return 1 in case number == 0 and when we translate this to a loop, we want to init the first value into 1.
Second value will also be 1 - run the recursive function (with debug prints) and see why.
After you see the Fib pattern, all you need to do is to implement a fib loop to return the number as shown in the video.
Thanks, that helped
Bumping the other guy's question. Why is it that 5 results in value of 1 in the DP array? if you take 1 step from 5 or 2 steps from 5 you'll be out of bounds either way; why does it not follow the same pattern as calculating the steps from 4 to 5?
man i had the same exact question, glad to see i'm not alone, did anyone figure this out yet?
Amazing. This is the best explanation I have seen for dynamic programming.
Happy it's helpful 😊
Just one question, at the end when you create the third variable, wouldnt be better to say two = one - two? if the goal of not using an array was to reduce memory cost that would fit