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.
class Solution: def climbStairs(self, n: int) -> int: dp = *(n+1) dp = dp = 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)
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
January 24, 2022
January 20, 2022
January 15, 2022