Climbing Stairs
ฝัง
- เผยแพร่เมื่อ 9 ต.ค. 2018
- For business inquiries email partnerships@k2.codes My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / programeme
Follow me on GitHub: github.com/kdn251 Discord: bit.ly/K2-discord - วิทยาศาสตร์และเทคโนโลยี
I thought I had to do permutations.
lol same
Lol same
lol same
Lmao same
lmao same
One of the best example problems on Dynamic Programming. Yes, Solve the sub problems first. Use them as base cases to solve the unknowns. Thanks for the video Kevin.
Anytime!
Your explanations are on point man. I plan on watching them all, thank you very much for making them. I have already shared your playlist with my other CS majors!
Thank you so much Daniel I'm so happy to hear the videos are helpful and thanks for helping spread my channel I really really appreciate that it helps me a lot!!!!
Exactly. They are on point!
This is magical. As a stat people with absolutely NO background knowledge in cs, your video is the ONLY thing I can understand after struggled in leetcode. plz keep doing more!
The best thing about your videos are it's short and easily explained.
I about to get laid off and need to prep for my coding interviews. I was getting stressed out and so overwhelmed with all the resources there are online. I'm glad I discovered this playlist! Really helpful, short and to the point!
did you find a job?
@@natnaelghirma2617 I did :) Thanks for asking.
@@RishModi nice man
Which company?? Experience?
After watching a bunch of other videos and reading articles, this is the solution that made the most sense. Thank you so much!
Do you mind explaining why dp[0] is 1 and not 0? I can't wrap my mind around it, since we're given either 1 or 2 steps. Not 0 steps.
++ someone please explain
storing the each stair and stairs is denoted as "1"(each steps) so he did dp[0]= 1 & dp[1] = 1 .....till last and we have array of stairs having each 1
1 means that there is only one path to get to that stair. Imagine you are on stair 0 (From bottom up approach, this means you're on the ground floor, not necessarily on a stair) how many ways can you get to where you're already at? If you take one step, your now on stair 1 so that's an invalid path. If you take two steps, you're now on stair 2 so that's an invalid path as well. If you stay right where you are, then that is technically a valid path because you've arrived there so the result is 1. In other words, if you're on stair 0 and you want to get to stair 0 you've already made it there so there is a path to get there by taking 0 steps, hence dp[0] = 1.
I understand the solution but I still can't grasp the intuition damnit
Simply make sets and visualise. let's say n=4
either boy can climb 1 step or 2 step means we can break 4 into 2 parts 4-2=2 && 4-1=3. Now again do same thing for 2 and 3 and so on. Calculate each path and sum them up you will get your answer
the intuition is a lie. None of these types of questions are "intuitive" unless you've seen it in a different form before. Don't feel bad.
@@TheIcecoldorange I agree. After solving a certain number of problems your brain starts to learn how to adapt to new problems of a similar kind but instead of telling you that "hey you're just used to seeing these kind of questions,so don't feel too smart", it starts to masquerade as "intuition". But that's not really the case. It's all a matter of conditioning and overfitting.
You can only takes steps of size 1 or size 2. At any given step on the staircase, there are only 2 ways you got there: 1. you took one step, or 2. you took 2 steps.
If you took 2 steps, it means your previous step-position was [i-2].
If you took 1 step, it means your previous step-position was [i-1].
That's it
Refer to the th-cam.com/video/QlT4HG93Gaw/w-d-xo.html for detail explanation..
Kevin that was awesome !! Loved your explanation :)
Tanmay Singh thanks and anytime! :)
Hey Kevin! Thank you for the video. I have been watching your video for a long time and they're very helpful!! :))
And I have one question about Dynamic programming. Dynamic programming problems are typically said to be difficult. Would you say the only way to get better at this type of questions would be solve as many problems related to this type of questions as possible? Because I think that it is very difficult to intuitively come up with a solution if I haven't solved this problem before. and this makes me feel like I just need to memorize the solutions so that I can solve it when I get this in a real interview.....:( is that how I am supposed to start for this type of questions? Thank you!
Oh wow this is similar to Fibonacci number problem. I was just able to undertsand that problem yesterday but this is making more sense on how to go about DP problems. Thank you
Hands down the best explanation. Thanks my dude
Just 5 minutes and pretty good explanation!
Thanks for this! It was very helpful for me to wrap my head around it.
Great videos man keep up the good work! I thinks dp[0] = 1 is not correct and confusing, you're saying that the ways to climb 0 steps is 1 ( you just don't climb), in that case dp[1] will be 2, you do not climb and just climb 1 step.
I think you dp[0] = 0, dp[1]=1, dp[2] =2, and then you start the loop from 3.
Thanks for the great videos.
Thank you! I just tried your suggestion with changing dp[0] = 0 and it fails :(. Same with initializing dp[0] = 0, dp[1] = 1, and dp[2] = 2 and then starting the loop at 3. I know it seems confusing but I still believe it makes sense. Dp always makes my head hurt lol
@@KevinNaughtonJr it needs a check first if (n == 0 || n == 1 || n == 2) return n; then you can set the dp[0], dp[1] and dp[2].
@@prezmoten ah gotcha, nice!!!
@@KevinNaughtonJr @prezmoten - Thanks guys
@@khurshidallam3966 Anytime!
Your explanation is so clear! Great work!
Yuhe Wang thanks Yuhe :)
I tried solving this using recursion and it worked but not for all test cases. The solution was really intuitive, Looks a easy problem but to get to it is what makes it a bit complicated.
Whenever Kevin sees Walmart in the companies list, his blood starts boiling xDD
why ??
Dang man this was nice to watch. I just started leetcoding and I'll make sure to stop by
Hey Kevin
If there's 1 way to climb no stairs (you don't climb em)..it would imply there are two ways to climb one stair(you either don't climb or you do climb just 1 step). Can you explain that? Also to reach dp(n) from dp(n-1) or dp(n-2), we still need to take one step, so shouldn't the loop be structured like dp(n) = d(n-1) + dp(n-2) + 1.
Yeah none of the videos I've seen explain why we don't add 1 to dp(n). Don't you still need to step one more time once you're at n-1 step?
yeah thats correct, step-0 shouldnt be counted, the correct logic is below
public static int climbStairs(int n) {
if (n
@@bhaskaro several videos into this problem and i couldnt get why that base case 0 makes no sense to me. Thanks so much. I hope others will see this comment.
Very good explanation, thanks!
This is fibo series lol nice !
amazing explanation! Thx!
I think we can solve this problem with same time complexity but way more efficient on space complexity if we just keep track of the last two index via creating variables rather than storing every element we calculated. Also using a while loop will be cheaper on space,(we won't consume the recursion stack) and will give an opportunity of easy debugging. Here is my code. (Yes my native language is JS and then Turkish :) )
let climbStairs = function(n) {
let prev = 1; // Case of we have only one step in the stair
if(n === 1) return prev;
let curr = 2; //Case of we have only two step in the step
n = n -2;
while(n > 0) {
[prev, curr] = [curr, prev+ curr];
n--;
}
return curr;
};
thanks for an easy explanation!
thanks for this! very intuitive explanation. i have my google technical phone interview in a couple of weeks and this is super helpful
Anytime Andy I'm super happy to hear the video was helpful! Lmk if there's anything I can do to hel you prepare and best of luck!
@@KevinNaughtonJr any chance of you making a video about your google/microsoft/etc. interviews?
@@KevinNaughtonJr
Would you like to make videos in-person discussion with Developers at BigN, like podcast or interview something?
I always wanted it on Joma Tech TH-cam channel.
I
Can you also make videos for Codeforces problems? Love your videos, really helpful
Great video. I'm trying to wrap my head around your base case. Wouldn't there be zero ways to climb the stairs if the input is zero? From my understanding in real-world terms, there would be no stairs to climb.
Thanks Samson. Yeah when I think about this base case too much it starts to make my head hurt lol. The way I try to think about it / rationalize it (which may be incorrect) is that if there are no stairs the one way to climb no stairs is doing nothing. I kinda like to think about it like the power set of a set in math. The empty set counts as a set even though it's empty. I hope that makes some sense? If not please lmk and I'll try to find a better way to explain it :)
@@KevinNaughtonJr this is like null set is also a set. So we have to count it.
Agreed you.
@@KevinNaughtonJr Hi, do you mind explaining it in a slightly different way? I still don't understand why dp[0] is 1
One of the best explanation i've seen so far
Great ♥️
Could u use more visualization tools or examples
Everything seems so easy with your code. Thanks
This is a great video. I am finally understanding dynamic programming; It makes more sense now. Thanks Kevin for taking the time and explaining it.
I don't know about everyone, but I can't get it into my head how the recurrence relation came up to be f(n) = f(n - 1) + f(n - 2). How did we conclude the resulting num of steps is summing steps at n - 1 with steps at n - 2 🤯
Just loved this solution....earlier tried with using Map etc but this sol really cool
Why is the recursive method so slow for this I set up base cases for 0,1,2 and tried Stairs(n-1) + stairs(n-2). It times out for when n >= 44. Even I have a little trouble grasping the dp[n-1] + dp[n-2] part a little bit. feel like we are not counting the ways of getting to nth step from the previous step and the step before previous.
What I understood is that if there are m kind of steps one can take (1, 2, 3, ..., m) while climbing stairs, there must be m ways how he can reach the n th step( i.e. from the n-1 th step to n th step, from the n-2 th step to n th step, from the n-3 th step to n th step, ..., from the n-m th step to n th step -> producing m ways). So, the number of ways to reach the n th step basically depends on the number of ways to reach the n-1 th, n-2 th, ...or the n-m th step. Thus, the recurrence relation.
What if instead of 1 and 2 steps, it is m and m hops. I have seen this question in other forums. Can you talk about that please?
Legend has it carlie is still trying to get to the other side
I know it works but not sure how. if dp[i] = dp[i-1] + dp[i-2], it doesn't make sense because you still have 1 way each from dp[i-1] and dp[i-2] to reach dp[i]. Hence, logically it should have been dp[i] = dp[i-1] + dp[i-2] + 2
It's not how many stairs, it's how many *ways*. Going back 1 step from top stair is just dp[top-1] ways, not dp[top-1]+1 and going 2 steps back from top stair is dp[top-1] not dp[top-1]+1.
Hey Kevin.. Just an absolute beginner on DP here.. I was confused like .. dp[2] = dp[1]+dp[0]; ---> You're doing this right when n=2; but when I go to n=3 in the loop, the code is not saving the value of dp[2] in any variable.. so my question is when the code is computing dp[3] = dp[2]+dp[1].. how will it replace the value of dp[2].. cause we have not saved it anywhere like we have for dp[1] and dp[0] in the top .Was kinda confused on that..
I like the recursion solution compared to the dynamic one
What I have seen is some of your solutions can be space-optimized and those are helpful for the interview.
Bruh they asked us this question in university after teaching us the bare basics of programming and i was stuck in it for a long time. Turns out its an effing google interview problem!!???
Does it mean that if we had three ways of climbing stairs - 1, 2, and 3 - we would need to solve it for 3 base bases and then dp[n] = dp[i-1] + dp[i-2] + dp[i-3]?
I think so
Awesome !!
Two important ways to under these types of problems and improve on them:
1. If you're doing some sort of DP to remember the result of two sub-problems, you can save space by using pointers.
2. When you're setting the 0th index in the DP array, think of it as the first SOLUTION, not as 0 stairs. The index doesn't represent the 0 case, so you still want error checking.
Yup! The actual "0 steps" is having an empty input array, which the problem guarantees won't happen (still good to mention/check for in an interview).
As soon as we have even one step, then we're in "populating solutions" territory. Don't worry about the Fibonacci base case of 0. It's not the same thing and doesn't apply.
There's actually a O(1) solution using fibonacci numbers but I don't really understand the math behind it. Would interviewers expect you to know that one or would I be fine giving them the O(n) DP solution?
can anyone explain why previous two results are taken ...like why only two ..why not prev result + something
No idea why dp(0) is actually 1 instead of 0. If dp(0) is 1, then intuitively dp(1) should be 2, because you either climb the stairs or DON'T climb the stairs like you did in dp(0)'s case. But setting dp(0) == 1 is the simplest way to make the formula work.
are u guys still together ?😂😂 Great explanation 👌
This was an awesome solution but I don't understand how the 0th case yields a 1. How can there be 1 way to climb 0 stairs? That doesn't click for me.
what about if they only can climb stair with 1 or 3 step? I am still confused
i have the same question
Solve the recurrence relation and you can get a solution in O(1) space and time complexity
You should provide the constant space answer for all your dp questions
I'm still a bit confused why you set your array to be the size of n+1? Everything else was great though, thanks!
Thanks Ayush! Here it's because it's inclusive of the last step :)
so I was confused on this too, but then I realized initializing an array like int[100] is of *size* 100, not up to index 100. So really the max index would be 99, so for int[n + 1] initialize, the max index is indeed n
This is exactly a Fibonacci problem masked into Stair climbing. Thank you for this.
Q: How do we decide when does a backtracking problem convert to a DP problem ? I am having hard time wrapping my head around this.
When you see your code is doing the same work multiple times, to avoid that we store our computations and use it when it is required again.
Dear Kevin, Thanks for the explanation. While solving this problem I had the same intuition but I am not understanding why are we not counting the number of ways to reach to n from n-1 to n-2
Shouldn't the recurrence relation be something like opt[i] = (opt[i-1]+1) + (opt[i-2] +2) . Which indicates that there is one way to reach from i-1 take 1 step and two ways from i-2 i.e 1,1 or 2.? This might be stupid but it'll be great if someone can explain this.
Hi! Asim, I think the ways from i-2 should only count one way in this case, since the 1,1 should be counted in the case from i-1. Think about this way: take 1 step from i-2, and now in i-1, so don't need consider take 1,1 from i-2.
@@jianjiazhang4746 yeah.. that leaves us with the expression : 1 + opt[i-1] + opt[i-2], ain't it
Just discovered your videos. Thanks for doing this, Kevin.
When you were asked this in your on-site, was this the first of two problems?
Did you at least mention the recursive solution first before optimizing with DP? When I first did this problem, I got TLE, and then resorted to DP.
Hey! Anytime; I hope you stick around and subscribe! I received something similar during my on-site in June. Hard to remember for sure but I think I mentioned dynamic programming first. In retrospect, it's probably better to talk about a recursive solution (without memoization) and then explain how it can be optimized with dp. For that round I believe I only received one problem. Once I had the dp solution we ran through some test cases and then talked about other potential optimizations.
Thanks for sharing that experience. Yeap! Have definitely subbed. I've got my on-site coming up soon and I'm anxious just thinking about it. I enjoy watching these videos. I found you through Yangshun's handbook that linked to your interviews repo on GH. Additionally, Refdash (in the README of the repo) isn't accepting new registrants anymore as they've just been acquired by Facebook and there's no word as to whether they'll be continuing with what they've been doing.
Anytime! You'll be fine!!! Feel free to reach out if you want any more help / advice.
maybe email me or something and I can try and help you more!
Pinged ya
Just got to this question on LeetCode. Looks similar to Fibonacci.
Yes definitely similar!
That's what made it click for me
It is the Fibonacci problem. Another solution is this:
def climbStairs(self, n, cache = None):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 1
if n == 1:
return 1
if cache is None: cache = {}
if n in cache: return cache[n]
result = self.climbStairs(n-1, cache) + self.climbStairs(n-2, cache)
cache[n] = result
return result
Great explaination as always.. I think the number of ways is Fibonacci Series (0,1,1,2,3,5,8....) Its pretty straight forward once you see patterns for n..
Here's my code:
class Solution {
public int climbStairs(int n) {
int ways=0,n1=1,n2=2;
if(n==n1)
return 1;
if(n==n2)
return 2;
for(int i=2; i < n; i++){
ways=n1+n2;
n1=n2;
n2=ways;
}
return ways;
}
}
Let me tell if I am missing something.. :)
You are right. It is the Fibonacci series.
Hi Kevin, I have one confusion in this question,Why there is dp[0] = 1, it should be zero(My understaning). Can you or comment reader,please help me/.
why is the base case 0 return 1? If you can only take either 1 or 2 steps, there should be 0 ways to get there right? since can't take either 1 or 2 steps to get to 0
What if n
Can we use permutation to solve this problem?
why it is n+1 when initialize the array
When the number of steps are calculated using the previous results - dp[i] = dp[i-1] + dp[i-2], assume one has reached to step i-1, then from i-1, it can reach to ith step in one way and from i-2 to i th step it can reach in 2 ways. Then why the final result is not dp[i] = dp[i-1] + dp[i-2] + 3 (adding 3 for the extra way from i-1 and i-2th steps). Am I missing anything here?
Did you understand why its not the case? I was thinking the same.
I don't understand why it wouldn't be more. If you're adding a step, there are more ways to combine the steps (I have the problem of taking 1, 2, or 3 steps at a time). Even if you say, you got to this step by getting to the n-1th step or the n-2th step or n-3th step, why do you add them together?
@Kevin what if we twist a question and say that you can climb 1 , 2 and 3 steps instead of 1 & 2 steps ?>
I think you'd do
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for (int i=3;i
Nice flex in startin
one doubt: why is no of ways to climb zero stairs = 1 ? (dp[0] =1 ) line 4
thank u brother 😄, btw can u explain the a[i] = a[i-1] +a[i-2]; line
Why there is 1 way to climb 0 stairs if we only got 2 options either climb 1 or 2 steps at a single time?
OK i think it’s essentially a fibonacci problem, now it makes sense. I never thought of calculating fibonacci sequence with dp haha
In all seriousness, the gall of calling this problem "easy". Ridiculous! I'll never reach the next level :sigh:
why declared the [n+1] array ?
Another way to solve in python, keep track of subproblems in a cache variable.
def climbStairs(self, n, cache = None):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 1
if n == 1:
return 1
if cache is None: cache = {}
if n in cache: return cache[n]
result = self.climbStairs(n-1, cache) + self.climbStairs(n-2, cache)
cache[n] = result
return result
Kevin, when we are given n=0 (i.e it will take 0 steps to reach to the top) in that case, I think, there is NO step that you can take as you are already on the top level, moreover, it is mentioned that we can take only 1 or 2 steps, we are not allowed to take 0 steps right ? 😅...BIG FAN ALREADY !!!!☺
Kevin, step-0 shuldnt be counted. i think below logic is correct.
public static int climbStairs(int n) {
if (n
If I am at position `i`, then either I got to `i` from `i-1` by taking 1 step, or from `i-2` by taking either 2x1step+ 1x2step. There for I should add `ways[i-1] +1` and `ways[i-2] + 2`
Why isn't the recursive relationship `ways[i]= (ways[i-2] + 2) + ways[i-1] + 1` ?
Just tried this problem and this was also my intuition. At least for the `(ways[i-2] + 2)` component, I can say there would only be one way counted here in addition to `ways[i-2]`, since `ways[i-1]` takes care of all the ways for index `i-1`. I'm still unsure exactly why it is not `ways[i]= (ways[i-2] + 1) + ways[i-1] + 1`. My intuition tells me there would be some overlap since `ways[i-1]` must also include some of the ways stored in `ways[i-2]`. It feels like applying fibonacci here is a mathematical way to get removing these duplicate ways. But I am not sure. Perhaps @Kevin or somebody else can step in and shed some light.
why did you return dp[n] ?
Very good explanation
This is basically Fibonacci seq with memoization
In my logic, there is actually 0 ways to climb 0 stairs. That is part that makes me confused.
Can someone help me why it takes 1 way to climb 0 steps?
But why is it a number of distinct paths?
Legend
I have a phone interview with Google on Tuesday. Do you have any recommendations on which types of problems I should focus on?
Best of luck! I would just recommend knowing their most frequently asked questions on LeetCode. Lmk if you have any other questions!
@@KevinNaughtonJr Thank you!
@@dephc0n1 Anytime!
@@dephc0n1 how did it go?
@@arabsforvr1908 Advice: Make sure to have an extra set of bluetooth headphones around. That way, when your main pair breaks 2 minutes before your interview you are still prepared. lol. Other than sounding unprofessional by using speaker phone, it went well.
This is simple Fibonacci Series using Dynamic Programming.
yep just disguised :)
please explain dry run of dp[i]=dp[i-1]+dp[i-2]..
dp[0] = 1?? If there are no stairs (0 stairs), then which is that 1 way to climb it?
I try to think of it like the power set in math.The empty set counts as a subset. It's confusing but essentially I think the 1 way to climb 0 stairs is basically by doing nothing (which just counts as a way)
@@KevinNaughtonJr ok.
he could have started with 1 and 2.. dp[0] make no sense. If you count doing nothing, then you can do nothing in any step(s) so dp[1] = 2 doing nothing and take 1 step
Hi Kevin, I have a phone interview with Google on Dec 4 for Test Engineer position. Can you please guide me on what type of questions can I expect in my interview?
Srinivasan Ramu hey Srinivasan congrats on getting the phone interview with google that’s amazing! I offer services to help people prepare for technical interviews on my Patreon page if you’re interested in checking it out here’s the link! www.patreon.com/KevinNaughtonJr
This sort of looks like the code to solve Fibonacci recursively.
That's exactly what it is ;)
Exactly man! I applied the fibonacci code and it worked correctly.
dp[i]= dp[i-1]+dp[i-2] // the two previous solutions will equal the current solution
what if we can only climb one step and 3 steps at a time?
I thought Leetcode was for super genius studs.
But I got your channel and now I am thinking, Which one I should be choosing, Google or Apple or Amazon?
Though I started "Leetcoding" yesterday only.
But the confidence I got, was because of you only bro.
Please keep uploading more videos.
Thank you so much!
Simple Python solution; 99% & 100% resp::
class Solution:
def climbStairs(self, n: int) -> int:
li=[0,1]
for x in range(2,n+1):
li.append(li[x-1] + li[x-2])
return sum(li[-2:])
What does dp stand for?
dynamic programming
One correction : No. of ways you can climb 0 stairs = 0, as it is clearly mentioned you can take either 1 or 2 steps.
The actual solution would be
dp[1]=1
dp[2] = 2
for(int i : 3 to N+1)
dp [i] = dp [i-1] + dp[i-2];
return dp[N]
Though the answer would be the same.
you can also use the recursion way with memoization
int ar[46]; // constrains from 1 to 45
int climbStairs(int n) {
if(n