Fibonacci as a Dynamic Programming Example

The Fibonacci recurrence is

$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}.$$

Naive recursion expands the same subproblems repeatedly and takes exponential time. Memoization evaluates each of the $n+1$ distinct states once instead of recomputing them; bottom-up evaluation makes their dependency order explicit.

Open full-size image

Green downward arrows write newly computed values into the cache; red upward arrows reuse them. When the right-hand call needs F5, its value is already stored, so the grey subtree is never expanded. The figure computes F7 = 13 using memoized recursion. The loop below goes one step further: it evaluates in order and keeps only the two values needed for the next addition.

Jeff Erickson, Algorithms, Figure 3.2 (p. 101); cropped from the PDF. · CC BY 4.0

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

State compression

To compute $F_n$, a table would retain every value from $F_0$ through $F_n$. The transition reads only the previous two, so two variables are sufficient:

• time: $O(n)$ arithmetic operations;
• auxiliary state: $O(1)$ integer variables;
• integer bit size still grows with $n$, so bit-complexity is not constant per addition for very large indices.

What the example teaches

Fibonacci is useful for recognizing overlapping subproblems and safe memory compression, but it is not a representative optimization problem. Faster doubling or matrix methods compute $F_n$ with $O(\log n)$ recurrence depth by using additional algebraic structure.

Avoid a mutable default dictionary in memoized Python examples; cache ownership and lifetime should be explicit.

Trace and integer cost

Before iteration k, (previous, current) equals (F_k, F_(k+1)). Simultaneous assignment preserves this invariant; after n iterations previous is the answer. For n=5 the successive pairs are (0,1), (1,1), (1,2), (2,3), (3,5), (5,8), giving 5. For n=0 the loop does nothing and returns 0; negative n is rejected. The input must be an integer.

The two variables hold a constant number of integers, not a constant number of fixed-size machine words for arbitrary n. Fibonacci numbers have Θ(n) bits. With ordinary linear-time integer addition, this loop therefore takes O(n²) bit operations and O(n) auxiliary bits.

assert fibonacci(0) == 0
assert fibonacci(5) == 5

Try a small index such as 6 in the USF Fibonacci workbench, comparing recursive, memoized, and table modes. Count distinct subproblem indices separately from total calls; this reveals what caching saves before the two-variable loop removes the table. The demo uses base values 1 and 1, so its numeric sequence is shifted relative to this page’s 0 and 1; compare the reuse pattern.

Source

• MIT OpenCourseWare: Dynamic Programming I

My reading · Opened notes are remembered in this browser.