DPAlgorithmaka fib, linear recurrence

Fibonacci Numbers

Compute F(n) = F(n-1) + F(n-2) in linear time by reusing the two previous values instead of recomputing them.

▶ VisualizePattern: Dynamic ProgrammingPractice (1)
Progress

Overview

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, …: every term is the sum of the two before it. It is the smallest problem that shows the whole DP toolkit — a recurrence, overlapping subproblems, a memoized top-down solver, a tabulated bottom-up solver, and a space optimization down to two variables.

The naive recursive definition fib(n) = fib(n-1) + fib(n-2) runs in O(φⁿ) (φ ≈ 1.618) because it recomputes the same subproblems exponentially many times. Recording each answer once collapses that to O(n). With matrix exponentiation (see Fast Exponentiation) it can even be O(log n), but the linear version is what interviews expect.

1D DPlinear recurrencememoizationrolling variablesO(n)

Intuition

A mental model before the formal terms.

Draw the call tree for fib(5): it calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2) again. fib(3) is computed twice, fib(2) three times, fib(1) five times. For fib(50) the duplication is astronomical — about 2×10¹⁰ calls to produce a number you could write on a sticky note.

Now imagine writing each answer on the sticky note the first time you compute it. The second request for fib(3) is a lookup, not a recomputation. The tree collapses into a single chain fib(1) → fib(2) → … → fib(n), and that chain is exactly what the bottom-up loop walks directly.

How it works

  1. State: dp[i] = the i-th Fibonacci number. One integer index fully describes a subproblem.
  2. Transition: dp[i] = dp[i-1] + dp[i-2] for i ≥ 2.
  3. Base case: dp[0] = 0, dp[1] = 1.
  4. Iteration order: increasing i from 2 to n, because each state depends only on smaller indices. Top-down memoization gets the same order implicitly through recursion.
  5. Answer location: dp[n].
  6. Space optimization: only the previous two values are ever read, so keep two variables a, b and slide them: a, b = b, a + b. Space drops from O(n) to O(1).

Why it works

Optimal substructure here is literal: F(n) is defined in terms of F(n-1) and F(n-2), and those values do not depend on how or why they were requested. So a value computed once for one caller is correct for every caller.

Overlapping subproblems: there are only n + 1 distinct subproblems (F(0) … F(n)) but the naive tree makes exponentially many calls. Caching guarantees each distinct state is solved exactly once, and each takes O(1) work, so the total is O(n).

Bottom-up correctness is by induction on i: if dp[i-1] and dp[i-2] are correct, then dp[i] computed from them is correct, and the bases are correct by definition.

Recognition

How to tell a problem wants this.

  • A quantity is defined by "the previous one plus the one before that" — Fibonacci, tribonacci, tiling a 2×n board with dominoes, counting binary strings without consecutive ones.
  • A naive recursive solution is obviously exponential and you can see the same call repeated in the tree.
  • n up to 10^5–10^7 rules out recursion depth in most languages and points at the iterative two-variable form.
“number of ways” → Dynamic Programming

Interactive visualization

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

Call stack (top first)
fib(6)
n=6
Recursion tree
fib(6)
memo
nfib(n)
1/23Call fib(6). Push a frame; the recursion tree grows one node.
Call in progressAnswered from memoReturned
PseudocodeLearn Fibonacci Numbers →
1fib(n):
2  if n <= 1: return n
3  if n in memo: return memo[n]
4  memo[n] = fib(n-1) + fib(n-2)
5  return memo[n]
Variables
n6
depth1
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1if n < 2: return n
2a = 0, b = 1
3for i in 2..n:
4  a, b = b, a + b
5return b

Implementations

1# Tabulated: dp[i] = F(i). Python ints never overflow.
2def fib(n: int) -> int:
31 · State table
4    if n < 2:
5        return n
6    dp = [0] * (n + 1)
72 · Base cases
8    dp[0] = 0
9    dp[1] = 1
103 · Transition
11    for i in range(2, n + 1):
12        dp[i] = dp[i - 1] + dp[i - 2]
134 · Answer
14    return dp[n]
15 
16 
17# Rolling variables, O(1) space
18def fib_rolling(n: int) -> int:
19    a, b = 0, 1
20    for _ in range(n):
21        a, b = b, a + b
22    return a
Walkthrough
  1. [0] * (n + 1) builds the table; multiplying a list of an immutable int is safe (no aliasing, unlike lists of lists).
  2. Base cases are set at 0 and 1 after the n < 2 guard so dp[1] exists.
  3. range(2, n + 1) is inclusive of n — the + 1 is the standard off-by-one to remember.
  4. fib_rolling uses tuple assignment a, b = b, a + b, which evaluates the right side fully before assigning.
Complexity (this implementation)
time O(n) · space O(n)

Rolling version O(1). Python ints are arbitrary precision, so F(1000) is exact; big-int addition becomes O(digits) for very large n.

Language notes
  • functools.lru_cache gives memoization for free but recursion depth is capped at ~1000 by default (sys.setrecursionlimit helps only up to the C stack).
  • Tuple swap a, b = b, a + b is the idiomatic rolling update — no temp variable needed.
  • Arbitrary-precision ints mean there is no overflow to worry about, only time proportional to digit count.
Common mistakes in this language
  • Calling the memoized recursive version with n = 10**5 — RecursionError. Use the loop.
  • Writing for i in range(2, n) and returning dp[n], which is still 0.
  • Placing @lru_cache on a method that takes an unhashable argument (like a list) — TypeError at call time.
Language differences that matter here
  • Overflow: C++ long long overflows at F(93) (undefined behaviour); JS/TS number silently loses precision after F(78); Python ints are exact forever.
  • Exact large values: use BigInt in JS/TS, __int128 or a big-int library in C++; Python needs nothing.
  • Recursion limits for the memoized version: Python ~1000 frames by default, JS/TS ~10^4, C++ typically ~10^5 — prefer the loop for large n in all four.
  • Tuple assignment a, b = b, a + b exists in Python; JS/TS destructuring allocates an array; C++ needs a temporary (or std::tie).

Complexity

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

Memoized version uses O(n) space for the cache and the recursion stack. Naive recursion is O(φⁿ). Matrix exponentiation gives O(log n).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
Avoid it when
  • When n is around 10^18 and you need F(n) mod m — use matrix exponentiation or fast doubling, O(log n).
  • When exact values are needed beyond F(92) in 64-bit languages — the result overflows; use big integers or modular arithmetic.

Alternatives

Fast ExponentiationRecursion & Backtracking

Common mistakes

  • Writing the memoized version without the cache and calling it "DP" — it is still exponential.
  • Off-by-one on which of the two rolling variables holds the answer after the loop.
  • Recursion depth: fib_memo(10**5) in Python overflows the default stack; use the iterative form for large n.
  • Overflow in Java/C++/Go: F(93) exceeds a signed 64-bit integer.

Interview patterns

  • Climbing stairs (1 or 2 steps) is Fibonacci shifted by one index.
  • Tribonacci and "ways to tile a 2×n board" — same structure with a different number of previous terms.
  • "Compute F(n) mod 10^9+7 for n up to 10^18" — matrix exponentiation on [[1,1],[1,0]].
Interview questions on this
Mock interviews

Example problems

Climbing Stairseasy