Climbing Stairs

You are climbing a staircase with n steps. Each move you can climb either 1 or 2 steps. How many distinct ways can you reach the top?

Examples

Input: 2 -> 2      # (1+1), (2)
Input: 3 -> 3      # (1+1+1), (1+2), (2+1)
Input: 5 -> 8

Constraints

• 1 <= n <= 45.

Approach — it's Fibonacci in disguise

To reach step n, your last move came from step n-1 (a 1-step) or step n-2 (a 2-step). Those are the only options, and they're disjoint, so:

ways(n) = ways(n-1) + ways(n-2)

with ways(1) = 1 and ways(2) = 2. That's the Fibonacci recurrence — solve it bottom-up in O(1) space.

Solution

def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    prev, curr = 1, 2          # ways(1), ways(2)
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr

Explanation

• Where the recurrence comes from: every path to the top ends with a final hop of size 1 or 2. Counting the ways to reach the step before that final hop, and summing, counts every path exactly once (no overlap, nothing missed).
• We carry only the two most recent counts, sliding them forward — identical machinery to the iterative Fibonacci.

Complexity

• Time: O(n).
• Space: O(1).

Interview tips

The skill being tested is deriving the recurrence, not memorizing it. Say "the last step is either 1 or 2" — that sentence is the whole solution. Follow-ups generalize to steps of size 1..k (sum the previous k terms).