Climbing Stairs

You are climbing a staircase with n steps. Each move you take either 1 step or 2 steps. Count the number of distinct ways to reach the top.

Example#

For n = 3 there are 3 ways: 1+1+1, 1+2, and 2+1. For n = 4 there are 5 ways. The counts follow the Fibonacci sequence.

Brute force note#

Recursively branch on each move (1 step or 2 steps) and count paths that land exactly on step n. This explores an exponential tree because the same subproblems (ways to reach a given step) are recomputed over and over.

Optimal approach#

Let ways(i) be the number of ways to reach step i. To stand on step i you arrived either from step i-1 (a 1-step move) or from step i-2 (a 2-step move), so ways(i) = ways(i-1) + ways(i-2), with ways(0) = 1 and ways(1) = 1. You only ever need the previous two values, so track them in two variables and roll forward.

 1def climb_stairs(n):
 2    if n <= 2:
 3        return n
 4    prev2, prev1 = 1, 2  # ways to reach step 1 and step 2
 5    for _ in range(3, n + 1):
 6        prev2, prev1 = prev1, prev1 + prev2
 7    return prev1
 8
 9
10print(climb_stairs(3))  # 3
11print(climb_stairs(4))  # 5
12print(climb_stairs(5))  # 8

Complexity#

Time is O(n): a single pass from step 3 to n. Space is O(1) because only the last two results are kept, unlike a full DP array which would use O(n).

This is the gateway problem for 1D dynamic programming. Study the recurrence-building process on the dynamic programming topic page, then continue through the 60-day curriculum.