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.

Example 1:

Input: n = 6
Output: 13
Explanation: The 13 ways include 1+1+1+1+1+1, 2+1+1+1+1, 2+2+2, and 1+2+2+1 - every ordered mix of 1-steps and 2-steps that sums to 6.

Example 2:

Input: n = 7
Output: 21
Explanation: ways(7) = ways(6) + ways(5) = 13 + 8 = 21.

Example 3:

Input: n = 1
Output: 1
Explanation: A single stair leaves exactly one option: one 1-step.

Constraints:

• 1 <= n <= 50

• The answer is guaranteed to fit in a 64-bit signed integer

Verification

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

Solution Breakdown

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=6: start prev_two=1, prev_one=2; step 3 gives current=3, step 4 gives 5, step 5 gives 8, step 6 gives 13, which is returned - the Example 1 answer.

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.