DPAlgorithmaka counting paths, ways to reach n

Climbing Stairs

Count the ways to reach step n taking 1 or 2 steps at a time — a Fibonacci recurrence in disguise.

▶ VisualizePattern: Dynamic ProgrammingPractice (3)
Progress

Overview

You stand at the bottom of a staircase with n steps and may climb 1 or 2 steps at a time. How many distinct sequences of moves reach the top? The answer for n = 1, 2, 3, 4, 5 is 1, 2, 3, 5, 8 — the Fibonacci numbers shifted by one.

It is the canonical "count the ways" DP: the state is "which step am I on", the transition is "where could I have come from", and the answer is a sum rather than a min/max. The same shape solves decoding a digit string, tiling a 2×n board, and reaching the end of an array with allowed jumps.

1D DPcountingFibonacciO(n)rolling variables

Intuition

A mental model before the formal terms.

To stand on step 4 you must have just arrived from step 3 (one step) or from step 2 (two steps). There is no other way in. So the number of ways to reach step 4 equals ways-to-reach-3 plus ways-to-reach-2 — and those two sets of paths are disjoint because their last move differs.

Concretely for n = 4: ways to reach 2 are {1+1, 2} (2 ways); ways to reach 3 are {1+1+1, 1+2, 2+1} (3 ways). So dp[4] = 3 + 2 = 5: 1111, 112, 121, 211, 22.

How it works

  1. State: dp[i] = number of distinct ways to reach step i from step 0.
  2. Transition: dp[i] = dp[i-1] + dp[i-2] — the last move was either a 1-step from i-1 or a 2-step from i-2. With a general step set S, dp[i] = Σ dp[i-s] for s ∈ S, s ≤ i.
  3. Base case: dp[0] = 1 (one way to be at the bottom: do nothing) and dp[1] = 1.
  4. Iteration order: i from 2 to n, since every state depends on smaller ones.
  5. Answer location: dp[n].
  6. Space optimization: two rolling variables for the 1-or-2 case; for step set S keep a window of max(S) values.

Why it works

Optimal substructure (here, "counting substructure"): every path to step i decomposes uniquely into a path to some earlier step plus one final move. The number of paths to that earlier step is the same regardless of what comes after it, so it can be reused.

The transitions partition the set of paths to i by the last move, so summing the parts counts each path exactly once — no double counting, no omissions.

Correctness by induction on i; the base dp[0] = 1 is what makes dp[2] = dp[1] + dp[0] = 2 come out right (1+1 and 2).

Recognition

How to tell a problem wants this.

  • The problem asks "how many ways" to reach a target position by a fixed set of moves.
  • The input is a single number n (or a 1D array) and moves are local (small jumps).
  • Brute-force enumeration of paths is exponential but the number of positions is linear.
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

012345678
11·······
1/16Base cases: there is 1 way to stand on step 0 (do nothing) and 1 way to reach step 1 (a single step).
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Climbing Stairs →
1dp[0] = 1; dp[1] = 1
2for i in 2 .. n:
3  dp[i] = dp[i-1] + dp[i-2]
4return dp[n]
Variables
n8
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1if n <= 1: return 1
2prev2 = 1  # dp[0]
3prev1 = 1  # dp[1]
4for i in 2..n:
5  cur = prev1 + prev2
6  prev2, prev1 = prev1, cur
7return prev1

Implementations

1# dp[i] = number of ways to reach step i with 1- or 2-steps
2def climb_stairs(n: int) -> int:
31 · State table
4    dp = [0] * (n + 1)
52 · Base cases
6    dp[0] = 1  # one way to stand still
7    if n >= 1:
8        dp[1] = 1
93 · Transition
10    for i in range(2, n + 1):
11        dp[i] = dp[i - 1] + dp[i - 2]
124 · Answer
13    return dp[n]
14 
15 
16# Generalized: arbitrary step sizes, still O(n * len(steps))
17def climb_stairs_steps(n: int, steps: list[int]) -> int:
18    dp = [0] * (n + 1)
19    dp[0] = 1
20    for i in range(1, n + 1):
21        for s in steps:
22            if s <= i:
23                dp[i] += dp[i - s]
24    return dp[n]
Walkthrough
  1. [0] * (n + 1) allocates the table; dp[0] = 1 records the single empty path.
  2. dp[1] = 1 is guarded by if n >= 1 so climb_stairs(0) does not raise IndexError.
  3. range(2, n + 1) visits every state up to and including n.
  4. The generalized version loops over steps and adds dp[i - s] for each reachable predecessor.
Complexity (this implementation)
time O(n) · space O(n)

O(n·k) for k step sizes. Exact for any n thanks to arbitrary-precision ints.

Language notes
  • Two rolling variables with tuple assignment prev2, prev1 = prev1, prev1 + prev2 give O(1) space.
  • lru_cache on a nested closure is the idiomatic top-down form, but recursion depth caps n around 1000.
  • sum(dp[i - s] for s in steps if s <= i) is a readable one-liner for the generalized transition.
Common mistakes in this language
  • dp[0] = 0 — the empty path must count as one way.
  • Using recursion with lru_cache for n = 10**5 and hitting RecursionError.
  • Forgetting % MOD when the statement asks for a modular count — Python will happily compute the huge exact value and time out.
Language differences that matter here
  • The counts grow like Fibonacci: C++ long long overflows near n = 91, JS/TS doubles lose exactness near n = 77, Python stays exact.
  • Iterating the step set: for (int s : steps) in C++, for (const s of steps) in JS/TS (for...in gives string keys), for s in steps in Python.
  • Memoized recursion depth: Python is the most restrictive (~1000); the loop is the safe form everywhere.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

With k allowed step sizes: O(n·k) time, O(n) or O(max step) space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • "Number of ways" to reach a position with a small fixed set of local moves.
  • As the stepping stone to House Robber (same state, max instead of sum) and to Grid DP (same idea in 2D — unique paths).
Avoid it when
  • When paths have costs and you want the cheapest — that is a min-plus recurrence (min cost climbing stairs), not counting.
  • When the number of ways only needs to be checked for feasibility ("can you reach") — a boolean DP or a greedy reach scan (Jump Game) is simpler.

Alternatives

Fibonacci NumbersRecursion & BacktrackingFast Exponentiation

Common mistakes

  • Setting dp[0] = 0 — then dp[2] comes out as 1 instead of 2. "Zero steps" is one valid (empty) path.
  • Confusing "distinct sequences of moves" with "distinct sets of steps landed on" — the former is what the recurrence counts.
  • Forgetting the modulus when the problem asks for the count mod 10^9+7 and n is large.
  • Applying the counting recurrence to a min-cost variant without swapping + for min.

Interview patterns

  • Climbing stairs with 1 or 2 steps (Fibonacci).
  • Decode Ways: dp[i] = dp[i-1]·[s[i] valid] + dp[i-2]·[s[i-1..i] valid].
  • Min cost climbing stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
  • Unique paths in a grid: the 2D version where you arrive from above or from the left.
Interview questions on this
Mock interviews

Example problems

Climbing StairseasyUnique PathsmediumJump Gamemedium