Fibonacci DP
Computing Fibonacci numbers — the sequence
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)— is the canonical first dynamic programming (DP) problem. The naive top-down recursion mirrors the math but takesΘ(φⁿ)exponential time because the recursion tree contains≈φⁿnodes (whereφ ≈ 1.618is the golden ratio); the same set ofndistinct subproblems is recomputedΘ(φⁿ⁻ᵏ)times each. Adding a memo (top-down memoization) or replacing the recursion with a left-to-right table fill (bottom-up tabulation) collapses the work toO(n)time,O(n)space; observing thatF(n)only depends on the previous two terms reduces space toO(1). Closed-form Binet’s formulaF(n) = (φⁿ − ψⁿ) / √5givesO(1)arithmetic but loses integer precision past roughlyn = 70under IEEE-754 doubles. Matrix exponentiation ofM = [[1,1],[1,0]]via repeated squaring achievesO(log n)arithmetic operations, which is the asymptotically fastest approach for arbitrary precision (modulo bignum multiplication cost). Generalizations include tribonacci (3-term recurrence), k-bonacci (k-term recurrence), and Lucas numbers (same recurrence, different seeds). Fibonacci is the seed problem from which the entire DP curriculum unfolds: the same “decompose by last decision” argument reappears in Climbing Stairs, House Robber, Coin Change, 01 Knapsack, and many others.
1. Intuition — Pairs of Rabbits and the Branching Recursion
Leonardo of Pisa (Fibonacci) introduced the sequence in 1202 in Liber Abaci via a rabbit-population thought experiment: start with one immature pair; every month, every mature pair produces a new immature pair, and every immature pair becomes mature. Counting pairs month-by-month produces 1, 1, 2, 3, 5, 8, 13, 21, …. Knuth’s TAOCP Vol. 1 §1.2.8 traces the modern formalization to Édouard Lucas (1878), who introduced the name “Fibonacci numbers” and studied the recurrence’s algebraic properties.
Strip away the rabbits and the recurrence is: F(n) = F(n-1) + F(n-2) with F(0) = 0, F(1) = 1. The (n+2)th term equals the (n+1)th plus the nth. To compute F(n), the most direct translation of the math into code is:
F(n):
if n <= 1: return n
return F(n-1) + F(n-2)
This is mathematically perfect and algorithmically catastrophic. Why?
The branching recursion tree. Computing F(n) calls F(n-1) and F(n-2). Computing F(n-1) calls F(n-2) and F(n-3). Computing F(n-2) calls F(n-3) and F(n-4). The same F(n-2) is computed twice (once as a child of F(n), once as a child of F(n-1)); the same F(n-3) is computed three times; the same F(n-4) is computed five times — the multiplicities themselves form Fibonacci numbers. The total node count of the recursion tree is exactly 2·F(n+1) − 1, which grows as Θ(φⁿ) where φ = (1 + √5)/2 ≈ 1.6180339887 is the golden ratio.
For n = 30, that’s about 2.7 million recursive calls. For n = 50, about 40 billion. For n = 100, more than there are atoms in the observable universe. The naive recursion is unusable past n ≈ 35 on a modern laptop in a tight loop.
The fix is one line: cache results. Since there are only n+1 distinct values to compute (F(0), F(1), …, F(n)), and we are computing them an exponential number of times with no parameters changing between calls, we can store each result the first time it is computed and return the cached value thereafter. This collapses the work from Θ(φⁿ) to Θ(n). That observation — exponentially many calls to a polynomially-sized set of subproblems means we’re doing exponential redundant work, and caching eliminates it — is the entire foundation of dynamic programming.
The Fibonacci recurrence is so elementary that the redundancy is glaringly visible. In more elaborate DP problems (Edit Distance, Longest Common Subsequence, 01 Knapsack) the redundancy is harder to see at a glance but the structure is the same: a polynomially-sized set of subproblems being recomputed exponentially often by the recursive expansion.
2. Tiny Worked Example — F(6)
State: F(k) = the k-th Fibonacci number. Recurrence: F(k) = F(k-1) + F(k-2). Base: F(0) = 0, F(1) = 1.
Bottom-up table fill:
| k | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| init | 0 | 1 | — | — | — | — | — |
| k=2 | 0 | 1 | 1 | — | — | — | — |
| k=3 | 0 | 1 | 1 | 2 | — | — | — |
| k=4 | 0 | 1 | 1 | 2 | 3 | — | — |
| k=5 | 0 | 1 | 1 | 2 | 3 | 5 | — |
| k=6 | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
F(6) = 8. We did exactly 6 additions to compute six values. Compare to the naive recursion: it would do 2·F(7) − 1 = 2·13 − 1 = 25 recursive calls. Even at n = 6 the naive form does 4× the work; by n = 30 the ratio is ~90,000×; by n = 50 it is ~10⁹×.
Naive recursion call tree for F(5) (annotated with multiplicities):
F(5)
/ \
F(4) F(3)
/ \ / \
F(3) F(2) F(2) F(1)=1
/ \ / \ / \
F(2) F(1) F(1) F(0) F(1) F(0)
/ \ =1 =1 =0 =1 =0
F(1) F(0)
=1 =0
Count of calls per distinct value:
F(0)called 3 timesF(1)called 5 timesF(2)called 3 timesF(3)called 2 timesF(4)called 1 timeF(5)called 1 time
Total: 15 calls = 2·F(6) − 1 = 2·8 − 1 = 15 ✓.
The multiplicities of F(0), F(1), F(2), F(3), F(4), F(5) are themselves F(5), F(4), F(3), F(2), F(1), 1 — Fibonacci eating itself. Knuth attributes this self-similarity observation to the structural beauty that draws mathematicians (and computer-science textbook authors) to use Fibonacci as the introductory DP example.
3. Pseudocode
# Naive — exponential, do not run for n > 30
fib_naive(n):
if n <= 1: return n
return fib_naive(n-1) + fib_naive(n-2)
# Top-down with memo — O(n) time, O(n) space
memo := empty map
fib_memo(n):
if n in memo: return memo[n]
if n <= 1: return n
result := fib_memo(n-1) + fib_memo(n-2)
memo[n] := result
return result
# Bottom-up table — O(n) time, O(n) space
fib_table(n):
if n <= 1: return n
dp := array of size n+1
dp[0] := 0
dp[1] := 1
for i in 2..n:
dp[i] := dp[i-1] + dp[i-2]
return dp[n]
# Bottom-up rolling — O(n) time, O(1) space
fib_rolling(n):
if n <= 1: return n
a, b := 0, 1 # F(0), F(1)
for i in 2..n:
a, b := b, a + b
return b
# Matrix exponentiation — O(log n) arithmetic ops
fib_matrix(n):
if n == 0: return 0
M := [[1, 1], [1, 0]]
return mat_pow(M, n)[0][1]
4. Python Implementation — Five Flavors
4.1 Naive Recursion (Pedagogical Counter-Example)
def fib_naive(n: int) -> int:
"""Exponential time. Do not call for n > ~35."""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)This is the version that translates the math one-to-one. It is also the version that should never run in production. Including it in the note is essential: every interview discussion of memoization should start by writing this version, then trace the redundancy in the call tree, then introduce the cache. Without the contrast, memoization sounds like a magic trick.
4.2 Top-Down with lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n: int) -> int:
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)The @lru_cache(maxsize=None) decorator from Python’s functools standard library memoizes the function on its argument tuple — here the single integer n. The decorator transforms the exponential recursion into linear time by intercepting calls and returning cached results when the same n recurs. Each of F(0), F(1), …, F(n) is computed exactly once; the rest of the call tree is short-circuited on cache hits. Time O(n), space O(n) for the cache plus O(n) for the recursion stack.
Risk: Python’s default recursion limit is sys.getrecursionlimit() = 1000. For n ≥ 1000 this implementation raises RecursionError. You can bump the limit with sys.setrecursionlimit(10**6) and possibly increase the OS thread stack size, but the bottom-up forms (4.3, 4.4) avoid the issue entirely.
4.3 Bottom-Up Table
def fib_table(n: int) -> int:
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]O(n) time, O(n) space. Iterative — no recursion stack. The table-fill order is trivial because dp[i] depends only on smaller indices. This form is most useful when you also need the intermediate values (e.g., to print the whole sequence up to F(n)).
4.4 Rolling Variables — O(1) Space
def fib_rolling(n: int) -> int:
if n <= 1:
return n
a, b = 0, 1 # invariant: a = F(i-2), b = F(i-1)
for _ in range(2, n + 1):
a, b = b, a + b # shift the window: (F(i-1), F(i))
return bO(n) time, O(1) space. The recurrence has look-back depth 2 — F(i) depends only on F(i-1) and F(i-2) — so we never need to remember more than the last two values. The simultaneous-assignment idiom a, b = b, a + b is Python’s clean way to shift the window forward by one step: both right-hand-side expressions evaluate using the old values of a and b before either left-hand-side variable is updated. This is the form interviewers most often expect, because it shows you understand the dependency structure well enough to optimize space. The rolling-array trick generalizes to any DP with bounded look-back depth (see Memoization vs Tabulation).
4.5 Matrix Exponentiation — O(log n) Time
The Fibonacci recurrence can be written in matrix form. Verify by direct multiplication:
[ F(k+1) ] [ 1 1 ] [ F(k) ]
[ F(k) ] = [ 1 0 ] [ F(k-1) ]
Expanding the right-hand side: top row is 1·F(k) + 1·F(k-1) = F(k+1) ✓; bottom row is 1·F(k) + 0·F(k-1) = F(k) ✓. Iterating this map n times starting from [F(1), F(0)]ᵀ = [1, 0]ᵀ yields [F(n+1), F(n)]ᵀ. Therefore
[ F(n+1) ] [ 1 1 ]ⁿ [ 1 ]
[ F(n) ] = [ 1 0 ] [ 0 ]
Computing Mⁿ via repeated squaring (the same divide-and-conquer trick used in modular exponentiation) takes O(log n) matrix multiplications. Each 2×2 matrix multiplication is constant time (8 multiplications, 4 additions), so the total arithmetic operation count is O(log n) — exponentially fewer operations than the linear approach.
def fib_matrix(n: int) -> int:
if n == 0:
return 0
def mat_mul(A, B):
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]],
]
def mat_pow(M, p):
result = [[1, 0], [0, 1]] # identity
base = M
while p > 0:
if p & 1:
result = mat_mul(result, base)
base = mat_mul(base, base)
p >>= 1
return result
M = [[1, 1], [1, 0]]
Mn = mat_pow(M, n)
return Mn[0][1] # F(n) sits at position [0][1] = [1][0]Caveat about the cost model. “O(log n) time” counts arithmetic operations as constant-cost, but F(n) itself has Θ(n · log₂ φ) ≈ 0.694 n bits, so the actual bignum-multiplication cost dominates for large n. With Karatsuba multiplication (O(d^{1.585}) for d-digit numbers), the true bit-complexity of computing F(n) is O(n^{1.585}), dominated by the largest multiplications near the top of the squaring chain. The “fast doubling” identity F(2k) = F(k)·(2·F(k+1) − F(k)) and F(2k+1) = F(k)² + F(k+1)² (derivable from the matrix identity but avoiding redundant matrix products — Wikipedia gives the equivalent forms F(2n) = (F(n−1) + F(n+1))·F(n) and F(2n−1) = F(n)² + F(n−1)², per the Fibonacci sequence article) is empirically faster in practice and is the standard implementation in libraries like SymPy. For interview purposes, the matrix form is the canonical answer.
Where the bignum crossover actually sits. A common mis-statement is that CPython “uses naive O(d²) multiplication up to ~70 digits, then switches to Karatsuba.” That is off by a base-conversion factor. The CPython source defines KARATSUBA_CUTOFF = 70, but the comment in Objects/longobject.c is explicit that this is measured in internal int digits “in base BASE”, not decimal digits: “For int multiplication, use the O(N**2) school algorithm unless both operands contain more than KARATSUBA_CUTOFF digits (this being an internal Python int digit, in base BASE)” (per CPython longobject.c, v3.12.0). On a standard 64-bit build each internal digit is PyLong_SHIFT = 30 bits (BASE = 2³⁰), so the schoolbook-to-Karatsuba transition happens at roughly 70 × 30 = 2100 bits ≈ 632 decimal digits — not 70 decimal digits. Because F(n) has about 0.209·n decimal digits, Karatsuba does not even engage until n ≈ 3000. Below that, both fib_matrix and fib_rolling operate on schoolbook-multiplied bignums, and the matrix form’s O(log n) operation count does not translate into a wall-clock win until n is large enough that the per-operation bignum cost is paid on far fewer (logarithmically many) — but much larger — operands.
4.6 Binet’s Closed-Form Formula
The characteristic polynomial of the recurrence F(n) = F(n-1) + F(n-2) is x² − x − 1 = 0, whose roots are φ = (1 + √5)/2 ≈ 1.6180339887 and ψ = (1 − √5)/2 ≈ −0.6180339887. The general solution to a linear homogeneous recurrence with these roots has the form F(n) = A·φⁿ + B·ψⁿ; plugging in F(0) = 0, F(1) = 1 gives A = 1/√5, B = −1/√5, yielding Binet’s formula:
F(n) = (φⁿ − ψⁿ) / √5
where φ = (1 + √5)/2 (golden ratio) and ψ = (1 − √5)/2 = 1 − φ (its conjugate).
Symbol-by-symbol:
φⁿ: dominant exponential growth term.ψⁿ: subdominant —|ψ| ≈ 0.618 < 1, soψⁿ → 0quickly.|ψ|¹⁰ ≈ 0.0083,|ψ|³⁰ < 10⁻⁶.- The denominator
√5normalizes the formula to integer outputs.
import math
def fib_binet(n: int) -> int:
phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2
return round((phi**n - psi**n) / math.sqrt(5))O(1) arithmetic operations (exponentiation is “O(1)” in the random-access machine model with native floats, though it is actually O(log n) if implemented via repeated squaring on integer exponents). The closed form is mathematically beautiful and useless in practice past n = 70:
The precision crossover is exactly n ≤ 70 (verified empirically on this platform’s IEEE-754 doubles): fib_binet(n) == fib(n) holds for every n from 0 through 70, and first fails at n = 71, where the true value F(71) = 308,061,521,170,129 exceeds what the double’s 53-bit mantissa can represent exactly, so the round() drifts. The mechanism: F(n) ≈ φⁿ/√5 and φⁿ first needs more than 53 bits of mantissa precisely around n = 71 (F(71) ≈ 3.08 × 10¹⁴, and 2⁵³ ≈ 9.0 × 10¹⁵ — but the intermediate φⁿ and the /√5 division compound rounding error, so the integer result becomes unreliable one step before the value itself reaches 2⁵³). The folklore “n ≤ 70” is correct; the occasional “n ≤ 71” claim is off by one.
For interview purposes, mention Binet only as a curiosity; never propose it as the answer when n could exceed ~70. For arbitrary precision, you would need to compute φⁿ symbolically (e.g., using Python’s decimal module with sufficient precision), at which point matrix exponentiation is simpler and comparably fast.
5. Complexity Summary
| Approach | Time (arithmetic ops) | Space | Notes |
|---|---|---|---|
| Naive recursion | Θ(φⁿ) ≈ O(2ⁿ) | O(n) stack | Exponential — never use for n > 30 |
| Memoized recursion | O(n) | O(n) cache + O(n) stack | Easy; stack-limited at n ≈ 1000 |
| Bottom-up table | O(n) | O(n) | No stack issues |
| Rolling variables | O(n) | O(1) | Interview-preferred form |
| Matrix exponentiation | O(log n) | O(1) | Best for n > 10⁹ |
| Fast doubling | O(log n) | O(log n) recursion | Smaller constant than matrix |
| Binet’s formula | O(1) (theoretical) | O(1) | Loses precision past n ≈ 70 |
The 2ⁿ-vs-φⁿ subtlety. Many texts call the naive recursion “O(2ⁿ)” — this is correct as a loose upper bound (the binary recursion tree has at most 2ⁿ nodes) but loose. The exact growth rate is Θ(φⁿ) ≈ Θ(1.618ⁿ), slower than 2ⁿ but still exponential. For n = 50, 2⁵⁰ ≈ 10¹⁵ while φ⁵⁰ ≈ 2.9 × 10¹⁰ — a factor of ~30000 difference. Both are “exponential and unusable,” so the distinction rarely matters in practice, but interviewers occasionally probe it.
Why is the recursion-tree node count exactly 2·F(n+1) − 1? Let T(n) = nodes in the tree rooted at F(n). T(0) = T(1) = 1. For n ≥ 2, T(n) = 1 + T(n-1) + T(n-2). Adding 1 to both sides: T(n) + 1 = (T(n-1) + 1) + (T(n-2) + 1) — the same Fibonacci recurrence. With T(0) + 1 = 2 = 2·F(1) and T(1) + 1 = 2 = 2·F(2), induction gives T(n) + 1 = 2·F(n+1), i.e., T(n) = 2·F(n+1) − 1. ∎
6. Generalization 1 — Tribonacci
Same idea, three-term lookback: T(0) = 0, T(1) = 1, T(2) = 1, T(n) = T(n-1) + T(n-2) + T(n-3). The sequence 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, … (LC 1137 N-th Tribonacci Number). The recurrence’s characteristic polynomial x³ − x² − x − 1 = 0 has dominant root the tribonacci constant ≈ 1.8392867552, so T(n) = Θ(1.839ⁿ). The same five algorithmic flavors apply: memo, table, rolling (now three variables), matrix exponentiation (now with a 3×3 matrix), closed form (with three roots).
7. Generalization 2 — k-bonacci
F_k(n) = sum_{j=1..k} F_k(n-j) for n ≥ k. Tetranacci (k = 4), pentanacci (k = 5), and so on. As k → ∞, the dominant root of the characteristic polynomial approaches 2, so the growth approaches 2ⁿ. The algorithmic recipes scale accordingly: rolling variables become a circular buffer of size k, matrix exponentiation uses a k × k companion matrix.
8. Generalization 3 — Lucas Numbers
Same recurrence, different initial conditions: L(0) = 2, L(1) = 1, L(n) = L(n-1) + L(n-2). Sequence: 2, 1, 3, 4, 7, 11, 18, 29, …. The Lucas numbers satisfy L(n) = φⁿ + ψⁿ (no √5 denominator) and several elegant identities like L(n) = F(n-1) + F(n+1). Useful in number theory (the Lucas–Lehmer primality test for Mersenne primes uses a Lucas-like recurrence).
9. Generalization 4 — Negative Indices and the Negafibonacci
Solving F(n) = F(n-1) + F(n-2) for F(n-2) gives F(n-2) = F(n) − F(n-1), which lets us extend the sequence to negative indices: F(-1) = 1, F(-2) = -1, F(-3) = 2, F(-4) = -3, F(-5) = 5, …. The pattern: F(-n) = (-1)^{n+1} · F(n). This is more curiosity than interview material but occasionally appears in advanced number-theory questions.
10. Diagram — The Recursion Tree’s Exponential Explosion
flowchart TD F5[F 5] --> F4[F 4] F5 --> F3a[F 3] F4 --> F3b[F 3] F4 --> F2a[F 2] F3a --> F2b[F 2] F3a --> F1a[F 1] F3b --> F2c[F 2] F3b --> F1b[F 1] F2a --> F1c[F 1] F2a --> F0a[F 0] F2b --> F1d[F 1] F2b --> F0b[F 0] F2c --> F1e[F 1] F2c --> F0c[F 0]
What this diagram shows. The naive (un-memoized) recursion tree of F(5). Notice the redundancy: F(3) appears twice, F(2) three times, F(1) five times, F(0) three times. Total node count is 2·F(6) − 1 = 15. As n grows, this multiplicity grows as Fibonacci itself — the number of times the leaves F(0) and F(1) are touched is exactly F(n) (a count whose own growth is Θ(φⁿ)). Memoization keeps the same recursion shape but assigns every distinct label a single cache slot; the second visit to any subtree returns instantly, collapsing the tree to the bold spine of distinct labels (F(5), F(4), F(3), F(2), F(1), F(0) — six total). Tabulation flips the picture entirely: instead of recursing top-down, walk F(0), F(1), F(2), …, F(5) left-to-right in an array, never building the tree. Matrix exponentiation abstracts away the recurrence and computes F(n) directly via Mⁿ in O(log n) operations. The diagram is the single best mental model for why DP exists: an exponentially-large recursion tree compresses to a polynomially-sized DAG of distinct subproblems. Storing each node once buys back exponential time at the cost of polynomial space.
11. Diagram — The Algorithmic Ladder
flowchart LR Naive["Naive recursion<br/>O(phi^n) time<br/>O(n) stack"] Memo["Top-down memo<br/>O(n) time<br/>O(n) cache"] Table["Bottom-up table<br/>O(n) time<br/>O(n) space"] Roll["Rolling vars<br/>O(n) time<br/>O(1) space"] Matrix["Matrix exp<br/>O(log n) time<br/>O(1) space"] Binet["Binet closed form<br/>O(1) time<br/>precision-limited"] Naive -->|"add cache"| Memo Memo -->|"invert direction"| Table Table -->|"drop old cells"| Roll Roll -->|"encode as matrix"| Matrix Matrix -.->|"mathematical curiosity"| Binet
What this diagram shows. A progression of optimizations, each transforming the previous algorithm by a single change. Adding memoization to naive recursion eliminates redundant computation but keeps the recursive structure. Inverting direction (top-down → bottom-up) gives tabulation, which is iterative and stack-safe. Dropping table cells we no longer read collapses to two rolling variables. Encoding the recurrence as matrix-vector multiplication and exponentiating via repeated squaring gives logarithmic time. Binet’s closed form short-circuits the algorithm entirely but at the cost of floating-point precision. Each arrow is a general DP optimization technique applicable to many problems — Fibonacci is the simplest substrate on which to learn the entire toolkit.
12. Pitfalls
12.1 The 2ⁿ vs φⁿ Confusion
Saying “naive Fibonacci is O(2ⁿ)” is correct as an upper bound but not tight. The exact growth is Θ(φⁿ). Either is fine in interview; if pressed for tightness, Θ(φⁿ) is the right answer.
12.2 Off-by-One in Indexing
Fibonacci has two competing indexing conventions:
- 0-indexed:
F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, …— modern standard, used by CLRS, OEIS A000045, Wikipedia, this note. - 1-indexed:
F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, …— older texts (including Knuth’s TAOCP).
LeetCode 70 (Climbing Stairs) implicitly uses a third convention where f(n) = F(n+1) in the 0-indexed scheme (because f(1) = 1, f(2) = 2 = F(3)). Always read the problem statement carefully; clarify which F(n) is meant.
12.3 Stack Overflow on Top-Down for Large n
Python’s default recursion limit is 1000. fib_memo(2000) raises RecursionError. Either bump the limit (sys.setrecursionlimit(10**6)) — which can crash the interpreter on bad inputs — or use the bottom-up forms.
12.4 Forgetting the Base Cases
F(0) = 0, F(1) = 1 is the modern standard. Setting F(0) = 1, F(1) = 1 (which some texts use) shifts the entire sequence by one. Stay consistent within a single solution.
12.5 Integer Overflow in Non-Python Languages
F(n) grows as φⁿ / √5, so it overflows fixed-width integers quickly. The signed 64-bit ceiling is 2⁶³ − 1 = 9,223,372,036,854,775,807 ≈ 9.22 × 10¹⁸. Checking the boundary: F(92) = 7,540,113,804,746,346,429 ≈ 7.54 × 10¹⁸ fits, while F(93) = 12,200,160,415,121,876,738 ≈ 1.22 × 10¹⁹ does not — so F(92) is the largest Fibonacci number representable in a signed 64-bit integer (verified by direct computation). F(93) still fits in an unsigned 64-bit integer (2⁶⁴ − 1 ≈ 1.84 × 10¹⁹), but F(94) ≈ 1.97 × 10¹⁹ overflows even that. In Python there is no concern (arbitrary precision); in C/C++/Java/Rust, use __int128/BigInteger/u128 for n > 92. For competitive-programming problems requiring F(n) mod 10⁹+7, perform the addition modulo the prime at every step.
12.6 Using Binet’s Formula for Large n
Past n = 70 (the formula is exact through n = 70 and first fails at n = 71, §4.6), phi**n loses integer precision. Don’t propose Binet as the “fast” answer in an interview without immediately stating the precision caveat — it makes you look like you’ve memorized a formula without understanding it.
12.7 Matrix-Exponentiation Sign and Order Errors
The matrix [[1, 1], [1, 0]] and the initial vector [1, 0]ᵀ = [F(1), F(0)]ᵀ must align so that Mⁿ · [1, 0]ᵀ = [F(n+1), F(n)]ᵀ. Swapping rows or columns of M, or starting from [F(0), F(1)]ᵀ, gives wrong indices. Derive the matrix from the recurrence on paper before coding.
12.8 Matrix Power for n = 0
Computing M⁰ = I and reading F(0) = I[0][1] = 0 works if you use the identity correctly. A common bug: returning Mn[0][0] = 1 instead of Mn[0][1] = 0 for n = 0. Special-case n = 0 at the top of the function.
12.9 Forgetting to Cache When Asked About “DP”
In a whiteboard interview, candidates sometimes verbally describe “use dynamic programming” but write the naive recursion anyway. Caching is the algorithmic content — verbalize the cache and write it.
12.10 Confusing Fibonacci Numbers with the Fibonacci Heap
Fibonacci Heap (Fredman & Tarjan 1987) is a separate data structure that uses Fibonacci-number bounds in its amortized analysis. It is unrelated to the algorithmic problem of computing Fibonacci numbers despite the name overlap.
13. Common Interview Problems
| Problem | LeetCode # | Pattern |
|---|---|---|
| Fibonacci Number | LC 509 | Direct Fibonacci computation |
| Climbing Stairs | LC 70 | Same recurrence, indexed f(n) = F(n+1) |
| N-th Tribonacci Number | LC 1137 | 3-term variant; same machinery |
| Min Cost Climbing Stairs | LC 746 | Cost variant; min-aggregating DP |
| House Robber | LC 198 | Same Fibonacci-shaped recurrence with values |
| Decode Ways | LC 91 | Fibonacci-shaped with conditional transitions |
| Unique Paths | LC 62 | 2D extension |
| Combination Sum IV | LC 377 | Generalized step sizes; permutation order |
| Pascal’s Triangle | LC 118 | 2D Fibonacci-style: each cell sums two predecessors |
14. Open Questions
- Resolved. The IEEE-754 double-precision crossover for Binet’s formula is exactly
n ≤ 70; it first fails atn = 71(F(71) = 308,061,521,170,129). Verified empirically (§4.6). - Resolved (mechanism, not exact wall-clock tie). The matrix-vs-rolling wall-clock crossover is governed by CPython’s bignum behavior: schoolbook multiplication is used until operands exceed
KARATSUBA_CUTOFF = 70internal 30-bit digits (≈ 632 decimal digits, i.e.F(n)forn ≈ 3000). The matrix form’s logarithmic operation count only pays off well into the bignum regime; the precise wall-clock tie depends on build and CPU but lies in the thousands ofn(§4.5). - Is fast doubling (
F(2k),F(2k+1)identities) provably better than matrix exponentiation in terms of bignum-multiplication count? Both doO(log n)operations; the constants differ (fast doubling avoids the redundant products of the full 2×2 matrix square). - What is the bit-complexity of the best known Fibonacci-computation algorithm? With FFT-based multiplication, the lower bound is
Ω(M(n))whereM(n)is the cost of multiplyingn-bit numbers (O(n log n)after the 2019 Harvey–van der Hoeven result).
15. See Also
- Memoization vs Tabulation — foundational DP framework; this problem is the textbook starting example
- DP State Identification — the meta-skill of recognizing DP structure
- Climbing Stairs — sibling problem, same recurrence shifted by one index
- House Robber — same Fibonacci-shaped DP with
maxaggregation and values - Coin Change — generalized “step sizes” Fibonacci-like counting DP
- 01 Knapsack — Fibonacci’s two-dimensional cousin
- Big-O Notation — for the
O(φⁿ) → O(n) → O(log n)complexity ladder - Hash Table — backbone of
lru_cachememoization - Fibonacci Heap — unrelated data structure that borrows the name
- SWE Interview Preparation MOC