Skip to content
GKgkml.dev
← Problem set
#70EasyDynamic programming

Climbing Stairs

The tell: Count the ways to reach a target using a fixed set of steps.

How you get there

  1. 1The last move came from either one step below or two below.
  2. 2So ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence.
  3. 3Only the last two values are ever needed, so two variables suffice.

Solution

Python
def climb_stairs(n: int) -> int:
    a, b = 1, 1          # ways to reach step 0 and step 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b
Time
O(n)
Space
O(1)

What goes wrong

Naive recursion without memoisation is exponential and times out well before n = 50.

Test yourself on DSANext: Edit Distance →