Skip to main content

Fibonacci as a Dynamic Programming Example

The Fibonacci recurrence is

F0=0,F1=1,Fn=Fn−1+Fn−2.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 reduces the reachable states to n+1n+1; bottom-up evaluation makes their dependency order explicit.

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 FnF_n, a table would retain every value from F0F_0 through FnF_n. The transition reads only the previous two, so two variables are sufficient:

  • time: O(n)O(n) arithmetic operations;
  • auxiliary state: O(1)O(1) machine words;
  • integer bit size still grows with nn, 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 FnF_n with O(log⁡n)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.

Source​