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;
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
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
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
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.
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!
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 🤔
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)
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.
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)
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
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
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 🙏👏❤🔥
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 }
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.
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.
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.
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...
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 :)
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 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.
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.
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.
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)])
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
For those looking for recursion solution - all tests case passed class Solution: def climbStairs(self, n: int) -> int: cache = {} def dfs(i): if i in cache: return cache[i] if i == n: cache[i] = 1 return cache[i] if i > n: return 0 cache[i] = dfs(i+1) + dfs(i+2) return cache[i] return dfs(0)
I would rather go with this approach: n=5, one =1 (can go to 1 in one way), two = 2 (can go to 2 in two ways ie 1+1, 2) 1 2 2 3 3 5 5 8 class Solution: def climbStairs(self, n: int) -> int: one, two = 1, 2 if n == 1: return one if n == 2: return two for i in range(n-2): temp = two two = two+one one = temp return two
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.
This is basically just Fibonacci sequence lmao. nice tutorial nonetheless and you did a great job explaining how to use DP. Here's a solution: int climbStairs(int n) { long long prev =1; long long curr =0; for(long i = 0; i
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.
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 :)
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
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.
Great video, but was just confused on one part: if you can only move either 1 or 2 steps, how is there 1 way to get to 5 from 5. 'Cause to get from 5 to 5, wouldn't you have to take 0 steps? And only 1 and 2 steps are options, right?
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).
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.
if you use fib memoization, you'll run into the issue of the 2 base cases of n-1 and n-2 indexes of your dp array, those duplicates will be removed into a set. Don't use hashmap memoization.
This one was confusing, because explanation was for bottom-up approach, but you coded up top-down approach. this one would be solution for bottom-up def climbStairs(self, n: int) -> int: prevSteps, curSteps = 0, 1 for i in range(n, 0, -1): curCache = curSteps curSteps = curSteps + prevSteps prevSteps = curCache return curSteps
Great Explanation seriously. They way you break down the problem and optimise it step by step is just great! Thank you so much for making these videos.
We can do O(log(n)) time and O(1) space. We search the value stairs(n) = f(n). We notice f(n+2) = f(n+1) + f(n). So we have : [f(n+2), f(n+1)] = [f(n+1), f(n)] * M where M is a 2 by 2 matrix I let you find. So by the associativity of the matrix product we have [f(n+1), f(n)] = [f(1), f(0)] * M^n. M^n can be computed in O(log n) time O(1) space using fast exponentiation. So O(n) time and space is not optimal.
I think no matter which angle you look at it, it’s the same as solving for Fibonacci? Which means we could do this bottom up tabulated approach as per the video, or top down, recursing/forloop through as per normal (means we start from step #5 as the root) since step #5 is dependent on n-1 and n-2 (same as fib) and caching the results (as per solving via DP for Fibonacci)
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?
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
🚀 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
ua-cam.com/video/UUaMrNOvSqg/v-deo.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 UA-cam!!
💯
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
> always start with a brute-force recursive solution- the best way to start solving any DP problem, *then* apply memoization/tabulation techniques
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
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
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
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.
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!
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 🤔
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)
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.
Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.
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)
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
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
Your explanations are so good, I'm so grateful that I get to watch your videos.
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 🙏👏❤🔥
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 have watched it from many other UA-camrs, no one even comes near you...
Crisp and clear... Very good explanation
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
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.
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.
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
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
class Solution:
def climbStairs(self, n: int) -> int:
if n
'just five lines' of but neat code. I appreciate your tutorials for easy-to-understand explanations
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!
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...
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 :)
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.
I love that you always start with a brute force solution, making the dp solution really natual in contrast.
two years later, we are still learning! Brilliant. Thank you!
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.
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.
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.
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)])
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
For those looking for recursion solution - all tests case passed
class Solution:
def climbStairs(self, n: int) -> int:
cache = {}
def dfs(i):
if i in cache:
return cache[i]
if i == n:
cache[i] = 1
return cache[i]
if i > n:
return 0
cache[i] = dfs(i+1) + dfs(i+2)
return cache[i]
return dfs(0)
Neetcode will go down as a legend in programming circles.
Where have you been all my life? Thank you and thank you again. Words have failed. Thank you.
whilst storing the initial value of "one" totally works, setting two = one - two does not require the temporary variable.
I'm getting OCD when I see you solved this without calling the orignal function back!.. Great work. Thank You.
I would rather go with this approach:
n=5, one =1 (can go to 1 in one way), two = 2 (can go to 2 in two ways ie 1+1, 2)
1 2
2 3
3 5
5 8
class Solution:
def climbStairs(self, n: int) -> int:
one, two = 1, 2
if n == 1:
return one
if n == 2:
return two
for i in range(n-2):
temp = two
two = two+one
one = temp
return two
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
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.
import math
class Solution:
def climbStairs(self, n: int) -> int:
counter = 0
sum = 0
while counter
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 got this memoaization approach by my own but this bottom up is fantastic.
You are genious!
This is basically just Fibonacci sequence lmao. nice tutorial nonetheless and you did a great job explaining how to use DP.
Here's a solution:
int climbStairs(int n) {
long long prev =1;
long long curr =0;
for(long i = 0; i
Thank you so much for taking the time to explain this. It makes a lot more sense now.
Both, the way you explain and the animations you provide, are truly awesome!
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
you explain like I'm a dumbass and this is why I like it
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 :)
first time listening about dynamic programming completely understood.
You have a talent of explaining hard concepts easily. 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
My interest in programming after watching this video 📈📈
Amazing explanation. Loved it
I cannot express how clever you are. Genius.
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.
to me, this is literally mind blowing, your explanation is perfect. thank you
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 🤣🤣🤣🤣
Very nice explanation, I understood the whole concept of Dynamic Programming in one video. Thank you!
You do not need a temp for any language. just do:
one = one + two
two = one - two
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
Great video, but was just confused on one part:
if you can only move either 1 or 2 steps, how is there 1 way to get to 5 from 5.
'Cause to get from 5 to 5, wouldn't you have to take 0 steps? And only 1 and 2 steps are options, right?
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).
One of the best explanations I have ever heard.
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.
int climbStairs(int n)
{
if(n
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
if you use fib memoization, you'll run into the issue of the 2 base cases of n-1 and n-2 indexes of your dp array, those duplicates will be removed into a set. Don't use hashmap memoization.
You can use python tuple syntax to avoid the need for a temporary variable: one, two = one + two, one
Also use _ instead of i.
Example 2 has two ways. 1 step + 1 step + 1 step or 1 step + 2 steps. The order doesn't mean anything thanks to the commutative property of addition.
This one was confusing, because explanation was for bottom-up approach, but you coded up top-down approach.
this one would be solution for bottom-up
def climbStairs(self, n: int) -> int:
prevSteps, curSteps = 0, 1
for i in range(n, 0, -1):
curCache = curSteps
curSteps = curSteps + prevSteps
prevSteps = curCache
return curSteps
normally I don't put any comments, But! here you smashed the problem! and I loved it!!!
Keep Up what you're doing! 👍
Great Explanation seriously. They way you break down the problem and optimise it step by step is just great! Thank you so much for making these videos.
The best ever explanation one could ever give. Thanks a lot!
We can do O(log(n)) time and O(1) space.
We search the value stairs(n) = f(n). We notice f(n+2) = f(n+1) + f(n). So we have :
[f(n+2), f(n+1)] = [f(n+1), f(n)] * M where M is a 2 by 2 matrix I let you find. So by the associativity of the matrix product we have [f(n+1), f(n)] = [f(1), f(0)] * M^n.
M^n can be computed in O(log n) time O(1) space using fast exponentiation.
So O(n) time and space is not optimal.
At every step we are having two decision to make out of set of choices {1,2}. Which can be written has
For n=5; 5C0 + 4C1 + 3C2 = 8
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
I think no matter which angle you look at it, it’s the same as solving for Fibonacci? Which means we could do this bottom up tabulated approach as per the video, or top down, recursing/forloop through as per normal (means we start from step #5 as the root) since step #5 is dependent on n-1 and n-2 (same as fib) and caching the results (as per solving via DP for Fibonacci)
This is the best explanation I have seen. Thanks
I love how intense the liner gets
Nothing easy about this 😅 except for the miraculous explanations of this channel as always! 🙏
HOW CAN ONE BE THIS GENIUS OMGGGGGG WONDERFUL APPROACH
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?
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…
such a good explanation of a fundamental problem