How many distinct ways can you climb n stairs if you can take 1 or 2 steps at a time?

How to think about it

Recognise the pattern

The signal is: “how many ways” combined with “choices at each step that only depend on nearby previous states.” This is the canonical intro to dynamic programming. The problem has two DP hallmarks: overlapping subproblems (computing ways(5) requires ways(4) and ways(3), which both require ways(3) and ways(2), etc.) and optimal substructure (the total ways from stair k depends only on ways from k-1 and k-2).

Define the DP

• State: dp[i] = number of distinct ways to reach stair i.
• Recurrence: dp[i] = dp[i-1] + dp[i-2]
• Base cases: dp[1] = 1, dp[2] = 2

Build the approach step by step

Brute force / naive recursion branches into two calls at every step: ways(n) = ways(n-1) + ways(n-2). Correct but O(2^n) — it recomputes the same subproblems exponentially many times.

Memoisation caches each result and brings time to O(n), space O(n).

Bottom-up (tabulation) fills an array from index 1 to n. Since each value only depends on the previous two, you only need two variables — no array at all.

n=5:
i:     1   2   3   4   5
dp:    1   2   3   5   8
           ^   ^
           |   |
       dp[i-2] dp[i-1]

Complexity

• Time — O(n): one pass from 3 to n.
• Space — O(1): only two variables needed, not an array.

Traps and variants