Fibonacci (DP)

O(n)

The Fibonacci numbers — 0, 1, 1, 2, 3, 5, 8, … — are defined by each term being the sum of the two before it. The naive recursive definition recomputes the same values an exponential number of times; dynamic programming fixes that by filling a table once, left to right: set the two base cases, then each cell adds the two to its left. That's linear time and the textbook first example of turning overlapping subproblems into a simple loop. The same one-row tabulation underlies climbing-stairs, tiling, and other linear recurrences. (Only the last two values are actually needed, so memory can be reduced to O(1).)

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Seed the base cases: F(0) = 0 and F(1) = 1.
  2. For each later index, add the two cells immediately to its left.
  3. Store the result and move one cell right.
  4. The last cell holds F(n) — computed in a single linear pass.

Pseudocode

1fibonacci(n):                       # O(n)2  dp[0] ← 0,  dp[1] ← 1              # base cases3  for i from 2 to n:4    dp[i] ← dp[i-1] + dp[i-2]        # sum the previous two5  return dp[n]6  # linear DP replaces exponential recursion