Climbing Stairs - Dynamic Programming - Leetcode 70 - Python

0:00 - Read the problem
3:55 - Brute Force
8:00 - Memoization
11:05 - Dynamic Programming
16:49 - Coding DP

leetcode 70

#dynamic #programming #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[max]

this is probably the hardest 'easy' tag question I've come across

[cloud-vietnam]

your videos should be in Leetcode's editorial solutions. Clear, concise, and so easy to understand.

[wrestlingscience]

17:40
" ah Yes.. makes sense so far"
17:50
"WAIT ITS OVER?!"

[CSBAjay]

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..

[kleadfusha]

The most underrated channel on YouTube!!

[xynergy]

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.

[techmemes]

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

[MrFrawsty]

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.

[sankalp]

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

[GateSlasHendrix]

instead of storing a temp variable, you can do this in python3+:
one, two = one + two, one

[floroz]

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!

[fnrir_]

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.

[ma-la]

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

[nicholascamarena]

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

[dazai]

Your explanations are so good, I'm so grateful that I get to watch your videos.

[aicancode]

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<=3:
return n

dp=[0]*(n+1)

dp[2] = 2
dp[3] = 3

for i in range(4, n+1):
dp[i] = dp[i-1]+dp[i-2]

return dp[n]

[nitiketshinde]

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

[prafulparashar]

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)

[jcoder]

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!

[dsptchr]

Literally the only person that actually explains this solution fully. It's unbelievable how badly others explain even the task.