Climbing Stairs | LeetCode | Solution Explained
70. Climbing Stairs is an easy LeetCode problem. We first look at the iterative dynamic programming (dp) approach followed by the more simpler constant space approach. I explain how we can think about this problem in terms of the classic Fibonacci problem.
Contents hide
Iterative DP
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0]*(n+1)
dp[0] = dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1]+dp[i-2]
return dp[n]
- Time: O(N)
- Space: O(N)
Space Optimizations
We only look at the last two values for computing ith value. Instead of an array, we can just keep ‘a’ and ‘b’ variables to compute ‘c’.
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2: return n
a = 1
b = 1
c = a + b
for _ in range(n-2): # n-2 because first two have already been completed
a = b
b = c
c = a + b
return c
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Reverse integer | InterviewBit | LeetCode | Solution Explained
January 24, 2022
Furthest Building You Can Reach | LeetCode | Solution Explained
January 20, 2022