Climbing Stairs

Problem

Staircase routing algorithms in build systems model multi-step jumps as combinatorial path counts. You can climb a staircase by taking 1 or 2 steps at a time. Given n stairs, return the number of distinct ways to reach the top.

Input: n = 2  → 2   (1+1, 2)
Input: n = 3  → 3   (1+1+1, 1+2, 2+1)
Input: n = 5  → 8

Verification

Trace by hand for n=4: prev_two=1, prev_one=2. Step 3: current=3, prev_two=2, prev_one=3. Step 4: current=5, prev_two=3, prev_one=5. Return 5. Verify by enumeration: (1+1+1+1), (2+1+1), (1+2+1), (1+1+2), (2+2) - five paths.

Solution

Approach: 1D tabulation collapsed to two rolling variables (a Fibonacci recurrence).

The count of ways to reach stair n is ways(n-1) + ways(n-2), because the move that lands you on n is either a single step from n-1 or a double step from n-2, and those two arrival sets are disjoint and together cover every path. That is exactly the Fibonacci recurrence, so the problem reduces to summing forward from the base cases. The base values anchor it: there is 1 way to stand on stair 1 and 2 ways to reach stair 2 (1+1 or 2). The solution short-circuits n <= 2 by returning n, which matches both base values. From stair 3 onward it keeps only the two most recent counts in prev_two and prev_one, computes current = prev_one + prev_two, then slides the window forward. Because each stair depends only on the previous two, a full array is unnecessary - two scalars carry all the state. Trace n=4: start prev_two=1, prev_one=2; step 3 gives current=3; step 4 gives current=5, which is returned, matching the five enumerated paths.

Edge cases: n = 1 and n = 2 are handled by the early return, so the loop never runs and never under-counts. n is a positive stair count, so there is no empty input to guard.

Complexity: O(n) time, O(1) space - one pass updating two scalars instead of an n-sized array.