Every time I think about your videos and your visual explantations, it makes me smile and want to solve more leetcode problems. Thanks for your effort in creating these amazing animations. Thank you for your hard work; it truly makes a difference.
so the hardes part of this problem to me specifically is realizing that the number of ways to climb n stairs is the number of ways to climb n-1 + the number of ways to climb n-2 stairs. my intuition is not intuitioning in this specific case. my brain just imagines that numberOfWays(n-1) is probably a subset of numberOfWays(n-2)...or the other way around. how did we logically get to a conclusion that NOW(n) = NOW(n-1)+NOW(n-2)? I have more than 400 LC problems under my belt so far, a fair share of which are DP-oriented and I kinda know how to optimize naive recursion using DP mostly, but for this specific problem I just didn't see the proper naive recursion function for optimization. This is what I had: public int climbStairs(int n) { return climb(n, 0, 0); } int climb(int n, int cur, int res) { if (cur==n) { return res+1; } if (cur>n) return res; res = climb(n, cur+1, res); res = climb(n, cur+2, res); return res; } and even though my code mentiones +1 and +2, it was not obvious for me how to turn this into dp (probably because the number of ways would just accumulate gradulally incrementing in recursive calls, and not adding two values generally speaking... Once you represented the naive recursion method in a different way on 1:58, it all clicked for me and the rest was a piece of cake from there. Even though I'm not finishing your video, I thank you for it. Good job!
An alternative solution that doesnt confuse you for index zero class Solution: def climbStairs(self, n: int) -> int: ways = [0] * (n + 1) # we set index zero to 0 ways[1] = 1 ways[2] = 2 for i in range(3, n + 1): ways[i] = ways[i - 1] + ways[i - 2] return ways[n]
"two_before" corresponds to the element at index 0 in the array. You could argue that logically, there should be 0 ways to climb 0 stairs...or maybe that counts as a way so there is 1 way. Either way, for the dynamic programming solution to work, there needs to be 1 + 1 = 2 ways to climb 2 stairs (at index 2), so we need to initialize both elements at index 0 and index 1 to be 1. The leetcode problem also seems to avoid this ambiguity by allowing us to assume n >= 1.
the best explanation among all else I've watched
Every time I think about your videos and your visual explantations, it makes me smile and want to solve more leetcode problems. Thanks for your effort in creating these amazing animations. Thank you for your hard work; it truly makes a difference.
Thank you for supporting the channel! I'm really glad you like the videos - more are on the way!
Best coding explanation I have ever seen, subbed
Most clear explanation for Dynamic programming I have ever seen....Thankyou so much....Please do more videos.....♥
so the hardes part of this problem to me specifically is realizing that the number of ways to climb n stairs is the number of ways to climb n-1 + the number of ways to climb n-2 stairs. my intuition is not intuitioning in this specific case. my brain just imagines that numberOfWays(n-1) is probably a subset of numberOfWays(n-2)...or the other way around. how did we logically get to a conclusion that NOW(n) = NOW(n-1)+NOW(n-2)? I have more than 400 LC problems under my belt so far, a fair share of which are DP-oriented and I kinda know how to optimize naive recursion using DP mostly, but for this specific problem I just didn't see the proper naive recursion function for optimization. This is what I had:
public int climbStairs(int n) {
return climb(n, 0, 0);
}
int climb(int n, int cur, int res) {
if (cur==n) {
return res+1;
}
if (cur>n)
return res;
res = climb(n, cur+1, res);
res = climb(n, cur+2, res);
return res;
}
and even though my code mentiones +1 and +2, it was not obvious for me how to turn this into dp (probably because the number of ways would just accumulate gradulally incrementing in recursive calls, and not adding two values generally speaking...
Once you represented the naive recursion method in a different way on 1:58, it all clicked for me and the rest was a piece of cake from there. Even though I'm not finishing your video, I thank you for it. Good job!
I love this channel so much! Really
An alternative solution that doesnt confuse you for index zero
class Solution:
def climbStairs(self, n: int) -> int:
ways = [0] * (n + 1) # we set index zero to 0
ways[1] = 1
ways[2] = 2
for i in range(3, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]
Quick question: Why is 'two_before' initialized to 1? Wouldn't it correspond to the array of index 1 as well? Thank you.
"two_before" corresponds to the element at index 0 in the array. You could argue that logically, there should be 0 ways to climb 0 stairs...or maybe that counts as a way so there is 1 way. Either way, for the dynamic programming solution to work, there needs to be 1 + 1 = 2 ways to climb 2 stairs (at index 2), so we need to initialize both elements at index 0 and index 1 to be 1. The leetcode problem also seems to avoid this ambiguity by allowing us to assume n >= 1.
It makes sense. Thank you!@gine
Thanks