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 th-cam.com/video/UUaMrNOvSqg/w-d-xo.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.
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
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!
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 🤔
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.
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
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)
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!
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 🙏👏❤🔥
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)
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.
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
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
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.
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 }
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)
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
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.
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...
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.
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 :)
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)])
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.
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.
@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.
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
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
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.
once you see the tree for n=5, you can just count how many 0's there are. how many 1's, etc. at this point you already have the answer is fib(n) and don't need to actually program anything.
There is also a O( log n ) time O( 1 ) space solution to this using the Fibanocci Formula :) One line of Python: return int((((1+math.sqrt(5))/2)**(n+1)-((1-math.sqrt(5))/2)**(n+1))/math.sqrt(5)) It's log n because the power ** operation takes log n time.
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.
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
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?
I can't tell if I think this problem is frustrating or beautiful. My intuition was: "okay, it's a combinatorics math problem". Eventually arriving at "result = sum(k in range [0, n/2] | nCk(n - k, k))" ... that's when I printed the sequence to the console. I just spent the best part of an hour creating an optimized nCk function, just to rediscover the fibonacci sequence.
IMO, most ideas that nerds call "beautiful" are simply ideas that require a thinker to hold ≥5 concepts (i.e. more than our four working memory slots) concurrently to grok.
You can get the solution by adding binomial coefficients. If x is the number of single steps and y the number of double steps, then: x = 5, y = 0 -> (5c0) x = 3, y = 1 -> (4c1) x = 1, y = 2 -> (3c2) and the sum is 1 + 4 + 3 = 8. The closed form solution is sum (n-j c j), j goes from 0 to int(n/2).
🚀 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
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
th-cam.com/video/UUaMrNOvSqg/w-d-xo.html
17:40
" ah Yes.. makes sense so far"
17:50
"WAIT ITS OVER?!"
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
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;
The most underrated channel on TH-cam!!
💯
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
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
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
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!
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 🤔
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.
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
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.
> always start with a brute-force recursive solution- the best way to start solving any DP problem, *then* apply memoization/tabulation techniques
Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.
Your explanations are so good, I'm so grateful that I get to watch your videos.
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)
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!
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 🙏👏❤🔥
two years later, we are still learning! Brilliant. Thank you!
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 it from many other TH-camrs, no one even comes near you...
Crisp and clear... Very good explanation
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
'just five lines' of but neat code. I appreciate your tutorials for easy-to-understand explanations
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
Where have you been all my life? Thank you and thank you again. Words have failed. Thank you.
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.
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
Neetcode will go down as a legend in programming circles.
first time listening about dynamic programming completely understood.
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
I'm getting OCD when I see you solved this without calling the orignal function back!.. Great work. 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.
Been learning DP since for ever, only watch your videos can make me wrap my head around, big thanks
The decision tree makes it so clear. Absolutely brilliant my friend!
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
you explain like I'm a dumbass and this is why I like it
You have a talent of explaining hard concepts easily. Thank you.
Both, the way you explain and the animations you provide, are truly awesome!
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)
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
Thank you so much for taking the time to explain this. It makes a lot more sense now.
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
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!
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.
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...
This is the best explanation I have seen. Thanks
I cannot express how clever you are. Genius.
I got this memoaization approach by my own but this bottom up is fantastic.
You are genious!
Very nice explanation, I understood the whole concept of Dynamic Programming in one video. Thank you!
to me, this is literally mind blowing, your explanation is perfect. thank you
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.
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 :)
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
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 🤣🤣🤣🤣
whilst storing the initial value of "one" totally works, setting two = one - two does not require the temporary variable.
class Solution:
def climbStairs(self, n: int) -> int:
if n
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)])
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.
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
My interest in programming after watching this video 📈📈
Amazing explanation. Loved it
One of the best explanations I have ever heard.
The best ever explanation one could ever give. Thanks a lot!
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.
Amazing. This is the best explanation I have seen for dynamic programming.
Happy it's helpful 😊
I love how intense the liner gets
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/...
man, you just made it eazzzz. Great explanation btw
A much better and clearer explanation of DP than my algorithm course…
HOW CAN ONE BE THIS GENIUS OMGGGGGG WONDERFUL APPROACH
This is crazy simple, man. Just love it 100%
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
this is a really good explanation!
Thanks!
Honestly the best video about introduction to dynamic programming.
You do not need a temp for any language. just do:
one = one + two
two = one - two
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
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.
Your Decision Tree explained memoisation succinctly. Thanks !!!
this is a very interesting solution . it makes lot of sense now how programming make life simple
Incredible incredible explaining. I really understood everything you said.
Thanks neetcode! I'm a better person now because of your videos!
once you see the tree for n=5, you can just count how many 0's there are. how many 1's, etc. at this point you already have the answer is fib(n) and don't need to actually program anything.
There is also a O( log n ) time O( 1 ) space solution to this using the Fibanocci Formula :) One line of Python:
return int((((1+math.sqrt(5))/2)**(n+1)-((1-math.sqrt(5))/2)**(n+1))/math.sqrt(5))
It's log n because the power ** operation takes log n time.
epic
Thank you, Neet. You make our lives easier!
a slight optimization for the swap without temp is to set two = one - two
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
What an explanation, I am by default follower now ;) Thanks for such a great explanation.
Nothing easy about this 😅 except for the miraculous explanations of this channel as always! 🙏
such a good explanation of a fundamental problem
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.
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
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?
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?
I can't tell if I think this problem is frustrating or beautiful.
My intuition was: "okay, it's a combinatorics math problem".
Eventually arriving at "result = sum(k in range [0, n/2] | nCk(n - k, k))"
... that's when I printed the sequence to the console.
I just spent the best part of an hour creating an optimized nCk function, just to rediscover the fibonacci sequence.
IMO, most ideas that nerds call "beautiful" are simply ideas that require a thinker to hold ≥5 concepts (i.e. more than our four working memory slots) concurrently to grok.
wow this is pretty awesome, really liked the way you break the problem
You can get the solution by adding binomial coefficients. If x is the number of single steps and y the number of double steps, then:
x = 5, y = 0 -> (5c0)
x = 3, y = 1 -> (4c1)
x = 1, y = 2 -> (3c2)
and the sum is 1 + 4 + 3 = 8. The closed form solution is sum (n-j c j), j goes from 0 to int(n/2).