Dynamic Programming

Dynamic programming sounds scary, but the core idea is simple: if a problem keeps asking the same smaller question over and over, answer each question once, write the answer down, and reuse it. The classic first example is the Fibonacci sequence. The slow way recomputes the same numbers thousands of times. The fast way fills a small table once.

The idea

Fibonacci is defined by fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1.

If you write that as plain recursion, fib(5) calls fib(4) and fib(3). But fib(4) also calls fib(3). So fib(3) gets computed twice — and fib(2) many times more. These repeated calls are called overlapping subproblems, and they make naive recursion cost O(2^n).

Dynamic programming fixes this. Instead of a recursion tree, we keep an array dp where dp[i] holds fib(i). We fill it from the bottom up. By the time we need dp[i-1] and dp[i-2], they are already sitting in the table — so computing dp[i] is a single addition.

Walk through it

Press Play on the right, or step with Next / Back. Notice the pattern repeat for every cell:

• The two cells just to the left — dp[i-1] and dp[i-2] — turn blue. Those are the values we read.
• We add them and write the sum into the current cell, which turns green and locks in place.
• The pointers i, i-1, and i-2 slide one step right, and the pattern repeats.

The key thing to see: each green cell is reused by later steps without ever being recomputed. That reuse is what turns an exponential algorithm into a linear one.

The code, line by line

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)              # the table
    dp[1] = 1                       # second base case
    for i in range(2, n + 1):       # fill left to right
        dp[i] = dp[i - 1] + dp[i - 2]   # reuse two earlier cells
    return dp[n]

• Lines 2-3 handle the base cases fib(0) = 0 and fib(1) = 1 directly.
• Line 4 creates the table dp, big enough to hold dp[0] through dp[n].
• Line 6 walks i from 2 up to n, filling one cell per step.
• Line 7 is the heart of it: every cell is the sum of the two before it. Because those two were already filled, this is O(1) work per cell.
• Line 8 returns the last cell — the answer.

This bottom-up style is called tabulation. The other style, memoization, keeps the recursion but caches each answer the first time it is computed; both turn O(2^n) into O(n).

Complexity

The table holds n + 1 numbers, so space is O(n). A neat trick: since each cell only needs the two before it, you can throw the rest away and keep just two variables — dropping space to O(1). That is a common interview follow-up.

When to use / pitfalls

Practice