Climbing Stairs is the #17 most asked LeetCode problem globally — and the single most important problem for understanding how Dynamic Programming works from first principles.
Our analysis of 10,385 verified interview questions across 259 companies shows it appeared 60 times across 25 companies — including Google, Amazon, Meta, Microsoft, Goldman Sachs, Citadel, Bloomberg, Grammarly, J.P. Morgan, and Intuit.
The problem is disguised Fibonacci. Once you see that ways(n) = ways(n-1) + ways(n-2), you understand the core DP pattern: break a problem into overlapping subproblems. Master this, then scale up to House Robber, Coin Change, and every 1D DP problem in interviews.
| Metric | Value |
|---|---|
| Total Interview Appearances | 60 verified mentions |
| Companies That Ask It | 25 companies |
| Global Rank | #17 out of 10,385 questions |
| Difficulty | Easy |
| Core Patterns | Dynamic Programming, Math, Memoization |
Google, Amazon, Meta, Microsoft, Goldman Sachs, Citadel, Bloomberg, Grammarly, J.P. Morgan, Intuit, AMD, Adobe, Apple, Barclays, Bolt, ByteDance, Cisco, Deloitte, Disney, Expedia, IBM, Infosys, Intel, and 2 more.
LeetCode #70 — Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input: n = 2 → Output: 2 (1+1, 2)
Input: n = 3 → Output: 3 (1+1+1, 1+2, 2+1)
Input: n = 5 → Output: 8To reach step n, you came from either step n-1 (took 1 step) or step n-2 (took 2 steps). So ways(n) = ways(n-1) + ways(n-2) with base cases ways(1) = 1, ways(2) = 2. That's exactly the Fibonacci recurrence.
dp[i] = dp[i-1] + dp[i-2] where dp[1]=1, dp[2]=2. The answer is dp[n]. Since you only need the last two values, you can use O(1) space with just two variables.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Recursion (no memo) | O(2ⁿ) | O(n) | TLE — exponential, never use |
| Top-down DP (memoization) | O(n) | O(n) | Good for explaining DP concept |
| Bottom-up DP (2 vars) | O(n) | O(1) | Optimal — use this in interviews |
def climbStairs(n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2 # ways(1), ways(2)
for _ in range(3, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1from functools import lru_cache
def climbStairs(n: int) -> int:
@lru_cache(maxsize=None)
def dp(i):
if i <= 2:
return i
return dp(i - 1) + dp(i - 2)
return dp(n)class Solution {
public int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
}var climbStairs = function(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
[prev2, prev1] = [prev1, prev1 + prev2];
}
return prev1;
};| Problem | Recurrence | Pattern |
|---|---|---|
| LC #70 Climbing Stairs | dp[i] = dp[i-1] + dp[i-2] | Fibonacci |
| LC #198 House Robber | dp[i] = max(dp[i-1], dp[i-2] + nums[i]) | Skip or take |
| LC #213 House Robber II | Run robber on [0..n-2] and [1..n-1] | Circular array |
| LC #322 Coin Change | dp[i] = min(dp[i-coin]+1) for each coin | Unbounded knapsack |
| LC #746 Min Cost Climbing Stairs | dp[i] = cost[i] + min(dp[i-1], dp[i-2]) | Climbing Stairs with cost |
Tag on DSAPrep.dev under Dynamic Programming.