Climbing Stairs
The problem
A staircase has n ≥ 1 steps. You can climb one or two steps at a time. Count the different ordered sequences of moves that reach the top exactly.
Example
n = 4 → 5: 1111, 112, 121, 211, 22
Need a hint?
The final move comes from one or two steps below.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Define ways(0) = 1 and ways(1) = 1. For each higher step, ways(i) = ways(i−1) + ways(i−2). Keep only the previous two counts. Treating zero steps as one empty sequence makes the recurrence consistent.
Complexity
O(n) time and O(1) auxiliary space under fixed-width arithmetic.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.