70. Climbing Stairs
easyAsked at AMDCount the distinct ways to climb n stairs taking 1 or 2 steps at a time. AMD uses this classic DP entry point to check whether candidates recognize overlapping subproblems and memoize — essential thinking for optimization passes in compilers and GPU shader pipelines.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in AMD loops.
- Glassdoor (2025-12)— AMD new-grad phone screens include Climbing Stairs as a DP warm-up to check memoization intuition.
- Blind (2025-08)— AMD interview prep threads list this as a common easy DP problem in first-round coding.
Problem
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?
Constraints
1 <= n <= 45
Examples
Example 1
n = 22Explanation: Two ways: 1+1 or 2.
Example 2
n = 33Explanation: Three ways: 1+1+1, 1+2, 2+1.
Approaches
1. Recursive with memoization (top-down DP)
climbStairs(n) = climbStairs(n-1) + climbStairs(n-2). Cache results to avoid recomputing.
- Time
- O(n)
- Space
- O(n)
function climbStairs(n) {
const memo = {};
function dp(i) {
if (i <= 1) return 1;
if (memo[i] !== undefined) return memo[i];
memo[i] = dp(i - 1) + dp(i - 2);
return memo[i];
}
return dp(n);
}Tradeoff: Intuitive for candidates who think recursively. O(n) after memoization but uses O(n) call stack + cache.
2. Bottom-up DP (space-optimized)
Recognize that only the previous two values matter. Use two variables instead of a full array.
- Time
- O(n)
- Space
- O(1)
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Tradeoff: O(1) space. Preferred at AMD where register-pressure and memory efficiency are first-class concerns. This is the Fibonacci sequence with a sliding window.
AMD-specific tips
AMD engineers optimize loops for register use and pipeline depth. The space-optimized two-variable approach maps directly to that mindset: instead of storing an array (cache lines), you keep only two live values (two registers). Name the connection explicitly: 'I only need the two most recent values, so I can keep them in two variables — no array needed.' This shows low-level efficiency intuition AMD values.
Common mistakes
- Naive recursion without memoization — exponential time, will TLE for n=45.
- Initializing the DP array incorrectly — dp[0]=1 (one way to be at the base) and dp[1]=1 (one step).
- Off-by-one errors in the loop bounds — start the loop at i=3 when using two variables initialized to dp[1]=1, dp[2]=2.
- Returning n for the base case instead of correctly handling n=1 and n=2 separately.
Follow-up questions
An interviewer at AMD may pivot to one of these next:
- What if you can take 1, 2, or 3 steps? (Generalize the recurrence.)
- Decode Ways (LC 91) — a direct extension with variable step encoding.
- How does memoization relate to instruction-level caching in a processor pipeline?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is this the Fibonacci sequence?
Because each state depends on exactly the two previous states: f(n) = f(n-1) + f(n-2). The base cases differ (f(1)=1, f(2)=2 vs Fibonacci's f(1)=1, f(2)=1) but the recurrence is identical.
Is the space-optimized O(1) version always better?
In practice yes — it uses two registers instead of an O(n) array. The only downside is you lose the ability to reconstruct the path, but this problem only asks for the count.