What Is Dynamic Programming?

The problem

You write the textbook definition of Fibonacci: fib(n) = fib(n-1) + fib(n-2). It reads beautifully. You ask for fib(50) and go make coffee. You come back, and it is still running. You bump it to fib(60) and now you could go on vacation.

Something is deeply wrong. The formula is correct, the code matches the formula, yet a laptop that does billions of operations a second chokes on the 50th number in a sequence a child can extend by hand. Where is all that time going?

A first attempt

Here is the naive recursion, exactly as the definition suggests.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Draw the call tree for fib(5) and the problem jumps out:

                    fib(5)
              /                \
          fib(4)              fib(3)
         /      \            /      \
     fib(3)    fib(2)    fib(2)    fib(1)
     /    \    /    \    /    \
  fib(2) f(1) f(1) f(0) f(1) f(0)

fib(3) is computed twice. fib(2) three times. As n grows, the same subproblems get recomputed an exploding number of times. The tree has about fib(n) leaves, so the running time is O(φⁿ) — exponential, where φ ≈ 1.618. That is why fib(50) never finishes: it makes over a billion calls to compute only 50 distinct answers.

The insight

Look again at that tree. There are only n distinct subproblems — fib(0) through fib(n). Everything else is a repeat. So the fix is almost embarrassingly simple:

Solve each subproblem once, write the answer down, and reuse it forever after.

That is the whole idea of dynamic programming. It applies whenever a problem has two properties:

• Overlapping subproblems — the same smaller problems recur again and again.
• Optimal substructure — the answer to the big problem is built from answers to smaller ones.

When both hold, you trade a little memory for an enormous amount of time.

How it works

The code

def fib(n):
    if n < 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

function fib(n: number): number {
  if (n < 2) return n;
  const dp = new Array<number>(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

class Solution {
    long fib(int n) {
        if (n < 2) return n;
        long[] dp = new long[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

long long fib(int n) {
    if (n < 2) return n;
    long long dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

long long fib(int n) {
    if (n < 2) return n;
    vector<long long> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Complexity

You only ever read the last two entries, so you can throw the whole array away and keep two rolling variables — dropping space to O(1) without changing the answer.

When to use it

Practice

Recap

• DP kills the exponential blowup of naive recursion by solving each subproblem once and reusing the result.
• It works when a problem has overlapping subproblems and optimal substructure.
• The recipe is always the same: define the subproblem, write the recurrence, set base cases, fill in order.