# 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

## 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
```
##### Tanishq Chaudhary

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.