Loading…
Climbing Stairs is a easy coding interview question covering dynamic programming, recursion — the kind asked at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and AI-first companies like Anthropic, OpenAI, and Nvidia.
You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. How many distinct ways can you climb to the top?
Example: n=3 -> 3 ways (1+1+1, 1+2, 2+1) Example: n=5 -> 8
Notice the pattern: this is Fibonacci.
Try it yourself first
In an interview you'd get about 15 minutes for a easy question. Sketch an approach before peeking — struggling is where the learning happens.
Stuck? Reveal them one at a time — each hint gives away a little more.
Ready to compare notes? The full solution, visualization, and complexity analysis are below.
The number of ways to reach step n equals the sum of ways to reach step n-1 (take 1 step) and n-2 (take 2 steps). This is exactly the Fibonacci recurrence. Space-optimised: only two variables needed.
| 1 | def climb_stairs(n: int) -> int: |
| ▶ | if n <= 2: |
| ▶ | return n |
| ▶ | a, b = 1, 2 |
| 5 | for _ in range(3, n + 1): |
| 6 | a, b = b, a + b |
| 7 | return b |
dp[1]=1, dp[2]=2 — base cases: 1 step = 1 way, 2 steps = 2 ways.
Key Insights
A full interview loop is more than one round. These are the others, each with what is on the site for it.