Dynamic Programming

Chapter 1: Fibonacci -- The Classic Example

The Fibonacci numbers are defined by the recurrence F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1. The series goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

The naive recursive implementation is elegant but disastrously slow:

python
def fib_r(n):
    if n <= 1: return n
    return fib_r(n - 1) + fib_r(n - 2)

This takes exponential time. Why? The recursion tree branches at every call. F(4) is computed on both sides of F(6). F(2) is computed five times just for F(6). Since F(n+1)/F(n) ≈ 1.618 (the golden ratio), computing F(n) requires at least 1.6ⁿ calls.

The picture with caching is dramatic. The recursion tree collapses from 25 nodes to just 11 -- each F(k) is computed exactly once and then looked up. This is the essence of dynamic programming: pay once, look up forever.

Chapter 2: Caching vs Dynamic Programming

There are two ways to fix the Fibonacci disaster:

Memoization (top-down caching): Keep the recursion but check a cache before computing. If the answer is already stored, return it. Otherwise, compute, store, and return.

python
cache = {}
def fib_c(n):
    if n in cache: return cache[n]
    if n <= 1: cache[n] = n
    else: cache[n] = fib_c(n-1) + fib_c(n-2)
    return cache[n]

True DP (bottom-up): Eliminate recursion entirely. Fill a table from small values to large, in an order that guarantees dependencies are ready.

python
def fib_dp(n):
    f = [0] * (n + 1)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

Both run in O(n) time. But true DP can be further optimized: since F(n) depends only on the last two values, we can use O(1) space instead of O(n).

Chapter 3: Binomial Coefficients

The binomial coefficient C(n, k) counts the ways to choose k items from n. It is defined by the recurrence from Pascal's triangle:

with base cases C(n, 0) = C(n, n) = 1. Why does this work? Consider whether the nth element is in the chosen subset. If yes, pick k-1 more from n-1 items. If no, pick all k from n-1 items. No overlap, all cases covered.

Computing C(n, k) via the factorial formula n!/(k!(n-k)!) is dangerous -- the intermediate factorials easily overflow, even when the final answer fits in an integer. The DP approach fills Pascal's triangle directly:

python
def binomial(n, k):
    C = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        C[i][0] = 1
        if i <= k: C[i][i] = 1
    for i in range(2, n + 1):
        for j in range(1, min(i, k + 1)):
            C[i][j] = C[i-1][j-1] + C[i-1][j]
    return C[n][k]

Chapter 4: Edit Distance -- The Problem

How different are two strings? The edit distance between strings P and T is the minimum number of character operations (insert, delete, substitute) to transform P into T.

Think about the last characters of each string. What could have happened?

The recursive version branches three ways at every position. Since most calls only reduce one index, the running time is at least 3ⁿ -- exponential. Computing edit distance between two 11-character strings takes several seconds recursively. Anything longer disappears into oblivion.

Chapter 5: Edit Distance by DP

The edit distance recurrence has only |P| × |T| distinct subproblems (all (i, j) pairs). The recursive version recomputes them exponentially many times. The fix: store results in a 2D table.

python
def edit_distance(s, t):
    m, n = len(s), len(t)
    D = [[0] * (n+1) for _ in range(m+1)]
    for i in range(m+1): D[i][0] = i  # delete all of s
    for j in range(n+1): D[0][j] = j  # insert all of t
    for i in range(1, m+1):
        for j in range(1, n+1):
            match = 0 if s[i-1] == t[j-1] else 1
            D[i][j] = min(
                D[i-1][j-1] + match,  # match/sub
                D[i][j-1] + 1,          # insert
                D[i-1][j] + 1           # delete
            )
    return D[m][n]

This runs in O(|P| × |T|) time and space. Each cell is computed once, and each computation is O(1). The table is filled row by row, left to right -- the same order you'd read a book.

Reconstructing the alignment: Store a parent pointer in each cell recording which of the three choices was optimal. Trace back from D[m][n] to D[0][0] to reconstruct the actual edit operations.

Chapter 6: Longest Increasing Subsequence

Given a sequence of numbers, find the longest subsequence that is strictly increasing. The subsequence doesn't need to be contiguous -- you can skip elements.

For example, in [3, 1, 4, 1, 5, 9, 2, 6], the LIS is [1, 4, 5, 9] or [1, 4, 5, 6] (length 4).

Define L[i] = the length of the longest increasing subsequence ending at position i. Then:

python
def lis(S):
    n = len(S)
    L = [1] * n  # every element is an LIS of length 1
    parent = [-1] * n
    for i in range(1, n):
        for j in range(i):
            if S[j] < S[i] and L[j] + 1 > L[i]:
                L[i] = L[j] + 1
                parent[i] = j
    return max(L)

This runs in O(n²) time. There exists a clever O(n log n) algorithm using binary search, but the O(n²) DP version illustrates the technique beautifully.

Tracing the actual subsequence: The parent array records, for each position, which earlier position extends to give the best LIS ending here. To reconstruct the subsequence, find the position with maximum L value, then follow parent pointers backward. This is the same trace-back technique used in edit distance and Floyd-Warshall.

LIS has surprising connections. It appears in patience sorting (a card game), the theory of Young tableaux (combinatorics), and the Erdos-Szekeres theorem (any sequence of length n² + 1 contains a monotone subsequence of length n + 1).

Chapter 7: The Partition Problem

Given a set of n integers, can you partition them into two subsets with equal sum? This is a classic NP-complete problem, but DP gives a pseudopolynomial algorithm -- polynomial in the value of the sum, not just the number of elements.

Let S be the total sum. We want to know: is there a subset summing to S/2? Define P[i][j] = true if we can make sum j using a subset of the first i elements.

Either we exclude element a_i (can we make sum j without it?) or include it (can we make sum j - a_i without it?).

python
def can_partition(arr):
    total = sum(arr)
    if total % 2 != 0: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in arr:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

Chapter 8: The DP Table Explorer

Watch the edit distance DP table being filled in cell by cell. See how each cell depends on its three neighbors (top, left, diagonal) and how the optimal alignment is traced back through parent pointers.

Chapter 9: Connections

Dynamic programming is arguably the most broadly useful algorithm design technique. Here is how it connects forward and backward: