Approach Summary
dp[i] = dp[i-1] + dp[i-2]. Equivalent to Fibonacci. Space-optimized: track only last two values.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: 1D Dynamic Programming Tabulation | O(n) | O(n) | Allocate an array dp where dp[i] represents total ways to reach step i. |
| 2 Approach 2: Fibonacci Space Optimization (Optimal) | O(n) | O(1) | Track only the last two step values using two scalar variables to achieve O(1) auxiliary space. |
Step 1: Baseline
Approach 1: 1D Dynamic Programming Tabulation
Time: O(n)
Space: O(n)
Initialize a 1D array dp of size n + 1. Set dp[1] = 1 and dp[2] = 2. Iterate from 3 to n filling dp[i] = dp[i - 1] + dp[i - 2]. This provides an explicit history of all steps, making debugging and visualization straightforward.
Approach 1: 1D Dynamic Programming Tabulation Implementation
Approach 1: 1D Dynamic Programming Tabulation
class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
vector<int> dp(n + 1, 0);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]function climbStairs(n) {
if (n <= 2) return n;
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
} Step 2: Most Optimized
Approach 2: Fibonacci Space Optimization (Optimal)
Time: O(n)
Space: O(1)
Because computing step i only depends on step i - 1 and step i - 2, there is no need to persist earlier calculations. Maintaining two pointers prev1 and prev2 and shifting them forward on each iteration yields an optimal O(1) space footprint.
Approach 2: Fibonacci Space Optimization (Optimal) Implementation
Approach 2: Fibonacci Space Optimization (Optimal)
class Solution {
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int prev1 = 1;
int prev2 = 1;
int curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;
}
return curr;
}
}class Solution {
public:
int climbStairs(int n) {
if (n == 1) {
return 1;
}
int prev1 = 1;
int prev2 = 1;
int curr = 0;
for (int i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;
}
return curr;
}
};class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
prev1, prev2 = 1, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev1 = prev2
prev2 = curr
return prev2function climbStairs(n) {
if (n === 1) return 1;
let prev1 = 1;
let prev2 = 1;
let curr = 0;
for (let i = 2; i <= n; i++) {
curr = prev1 + prev2;
prev1 = prev2;
prev2 = curr;
}
return curr;
}Edge Cases to Watch
- n = 1 (only 1 way: take 1 step; returns 1 immediately)
- n = 2 (2 ways: [1, 1] or [2]; returns 2)
- Large values up to n = 45 (computes under 1ms without overflow in 32-bit signed integer limits)
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Count ways to reach nth step
- Fibonacci-like recurrence
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
DP Math Memoization
Frequently Asked Questions
What is the optimal time and space complexity for Climbing Stairs?
The optimal solution for Climbing Stairs achieves O(n) runtime complexity and requires O(1) auxiliary space. Time complexity is O(n) because we perform a single linear loop from 2 to n. Space complexity is O(1) since we only keep track of two previous step counts in scalar variables.
How do I identify that Climbing Stairs requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Count ways to reach nth step; Fibonacci-like recurrence. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Climbing Stairs?
Essential edge cases to verify include: n = 1 (only 1 way: take 1 step; returns 1 immediately); n = 2 (2 ways: [1, 1] or [2]; returns 2); Large values up to n = 45 (computes under 1ms without overflow in 32-bit signed integer limits). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Climbing Stairs?
Climbing Stairs is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Adobe, Apple.