Climbing Stairs Solution

Problem

You need to reach the top of a staircase with n steps. On each move you can climb either 1 or 2 steps. Count how many distinct sequences of moves get you to the top.

Input: n = 4
Output: 5
Explanation: The five ways are (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), and (2,2).

Intuition

The number of ways to reach step n equals the ways to reach step n-1 (then take one step) plus the ways to reach step n-2 (then take two steps). This is the Fibonacci recurrence — every result depends only on the two before it, so the problem telescopes into a simple iteration from the bottom up.

Approach 1 — Bottom-Up DP

Build a table where dp[i] stores the number of ways to reach step i, filling left to right with the recurrence dp[i] = dp[i-1] + dp[i-2].

Handle n <= 2 directly as base cases.
Allocate dp of size n+1 and seed dp[1] = 1, dp[2] = 2.
For each step from 3 to n, set dp[step] = dp[step-1] + dp[step-2].
Return dp[n].

1def climbStairs(n: int) -> int:
2    if n <= 2:
3        return n
4    dp = [0] * (n + 1)
5    dp[1] = 1  # one way to reach step 1: a single 1-step move
6    dp[2] = 2  # two ways to reach step 2: (1,1) or (2)
7    for step in range(3, n + 1):
8        dp[step] = dp[step - 1] + dp[step - 2]
9    return dp[n]

Time: O(n) — one pass through all steps.
Space: O(n) — the DP table holds one entry per step.

Approach 2 — Space-Optimized (Two Variables)

Since each entry depends only on the previous two, we replace the full table with two rolling variables and reduce memory from O(n) to O(1).

Initialize prev_two = 1 and prev_one = 1 (representing f(0) and f(1) respectively).
For each step from 2 to n, compute current = prev_one + prev_two, then slide both variables forward.
Return prev_one after the loop.

1def climbStairs(n: int) -> int:
2    prev_two, prev_one = 1, 1  # f(step-2) and f(step-1); handles n=1 with no iterations
3    for _ in range(2, n + 1):
4        current = prev_one + prev_two
5        prev_two = prev_one
6        prev_one = current  # slide the window forward before the next iteration
7    return prev_one

Time: O(n) — same single pass.
Space: O(1) — only two integers regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Bottom-Up DP	O(n)	O(n)	When you need the full table (e.g., to reconstruct paths or adapt to a variant)
Space-Optimized	O(n)	O(1)	Default choice — cleaner and uses constant memory

Common Mistakes

Wrong base case for n = 1: Returning 0 or 2 instead of 1. There is exactly one way to reach step 1 (take a single step), so dp[1] = 1.
Off-by-one in array size: Allocating dp[n] instead of dp[n+1] causes an out-of-bounds error when writing to dp[n] directly.
Overwriting before reading in the two-variable approach: Setting prev_two = prev_one before computing current loses the old prev_two and produces wrong results from step 3 onward.
Both variables initialized to 0: Forgetting that the Fibonacci seeds here are both 1, not 0 — dp[1] = 1 and the conceptual dp[0] = 1.
Returning dp[n-1] instead of dp[n]: A common slip when mixing 0-indexed intuition with this 1-indexed formulation.

Climbing Stairs — Solution