LeetCode #70: Climbing Stairs | Dynamic Programming

0:00 Problem overview
0:48 Recursive solution
2:17 Recursive tree visualization
4:18 Dynamic programming solution
7:00 Dynamic programming code walkthrough

#leetcode #coding #programming #algorithms

[RamPageMMA]

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.

[mick]

the best explanation among all else I've watched

[darkevermgk]

Best coding explanation I have ever seen, subbed

[vigneshs]

Most clear explanation for Dynamic programming I have ever seen....Thankyou so much....Please do more

[zeeg]

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!

[mark-]

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]

[jpkeys]

Quick question: Why is 'two_before' initialized to 1? Wouldn't it correspond to the array of index 1 as well? Thank you.