Climbing Stairs
Problem Description
Count the ordered ways to climb n steps when each move climbs one or two steps. For n=3, the ways are 1+1+1, 1+2, and 2+1, so the answer is 3. The sequences 1+2 and 2+1 count separately because the move order differs.
This lesson defines n=0 as one way: take no moves. Negative step counts are invalid. If an interview uses another convention for zero, agree on it before coding.
Think about: What could the final move into step n have been?
Worked solution Open when you’re ready to compare your approach
Two-state dynamic programming
Let ways(i) be the number of ways to reach step i. The final move comes from i-1 or i-2, so ways(i) = ways(i-1) + ways(i-2). Keep only the last two counts.
def climb_stairs(n: int) -> int:
if n < 0:
raise ValueError("n must be nonnegative")
previous_two, previous_one = 1, 1
for _ in range(2, n + 1):
previous_two, previous_one = previous_one, previous_two + previous_one
return previous_one
Worked trace
The base counts are ways(0)=1 and ways(1)=1. For step 2, the two possibilities are 1+1 and 2, so the count is 2. For step 3, the count becomes 1+2=3; for step 4, it becomes 2+3=5. Each value adds disjoint sets of paths classified by their final jump.
Why it works
Every valid path to step i ends with exactly one of the two allowed jumps. Removing that final jump leaves a valid path to i-1 or i-2; conversely, appending the appropriate jump to such a path creates a unique path to i. Thus the recurrence neither misses nor double-counts a path. The loop computes counts in increasing order so required earlier values are available.
Time is O(n), and the rolling state uses O(1) variables. The returned integer itself grows in bit length with n. A recursive solution without memoization recomputes the same subproblems many times. If moves of three steps are also allowed, add ways(i-3) and revisit the base cases rather than reusing this code unchanged.
Step 5 of 7 · Core interview practice
Put this step into practice.
Derive the base cases and explain the meaning of each rolling variable.
Enable JavaScript to save progress. You can still continue through the path.
