Climbing Stairs

Problem

You're climbing a staircase with n steps. Each move you take either 1 or 2 steps. Count how many distinct sequences of moves reach the top.

Your signal — what pointed here?Your skeleton — the reusable shape

Signal

"Count the ways to reach step n" where each step's count is built from a fixed set of earlier steps is a fib-shaped counting recurrence — the answer at position i is just a sum of answers at a few positions before it.

Approach

To reach step i, your last move was either a 1-step from i-1 or a 2-step from i-2. Every distinct sequence ending at i is one of those two cases, so the count at i is the sum of the counts at i-1 and i-2. Base cases: 1 way to stand at step 0 (do nothing), 1 way to reach step 1.

Skeleton

prev2, prev1 = 1, 1   # ways to reach step 0, step 1
for i in range(2, n + 1):
    prev2, prev1 = prev1, prev1 + prev2
return prev1

Solution

def climb_stairs(n: int) -> int:
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Complexity

O(n) time, O(1) space — two rolling variables instead of a full dp array, since each step only ever needs the previous two values.

Pitfalls

Writing the full recursive version without memoization re-solves the same subproblems exponentially — O(2ⁿ) instead of O(n).
Off-by-one on the base cases: n = 0 and n = 1 both have exactly 1 way, not 0 — get this wrong and everything after it is shifted.
Recognizing this is literally Fibonacci is the whole trick; don't overthink it into something more complicated than "sum of the previous two".