4 min read
On this page

Dynamic Programming

Dynamic programming (DP) solves optimization and counting problems by breaking them into overlapping subproblems, solving each once, and storing results.

Key Properties

Overlapping Subproblems

The same subproblems are solved multiple times. DP stores results to avoid recomputation.

Example: Fibonacci. fib(5) calls fib(4) and fib(3). fib(4) calls fib(3) and fib(2). fib(3) is computed twice (and fib(2) three times, etc.).

Optimal Substructure

An optimal solution to the problem can be constructed from optimal solutions to subproblems.

Example: Shortest path. The shortest path from A to C through B consists of the shortest path from A to B plus the shortest path from B to C.

Two Approaches

Top-Down (Memoization)

Write the natural recursive solution, then cache results.

FUNCTION FIB(n, memo)
    IF memo[n] is not empty THEN RETURN memo[n]
    IF n ≤ 1
        result ← n
    ELSE
        result ← FIB(n - 1, memo) + FIB(n - 2, memo)
    memo[n] ← result
    RETURN result

Pros: Only computes needed subproblems. Natural recursive thinking. Cons: Recursion overhead (stack). Hash map/array lookup.

Bottom-Up (Tabulation)

Fill a table iteratively from smallest subproblems to largest.

FUNCTION FIB(n)
    IF n ≤ 1 THEN RETURN n
    dp ← array of size n + 1, initialized to 0
    dp[1] ← 1
    FOR i ← 2 TO n
        dp[i] ← dp[i - 1] + dp[i - 2]
    RETURN dp[n]

Pros: No recursion overhead. Often faster. Can optimize space. Cons: Must determine computation order. May compute unnecessary subproblems.

Space Optimization

Often only the last few values are needed:

FUNCTION FIB(n)
    IF n ≤ 1 THEN RETURN n
    a ← 0, b ← 1
    FOR i ← 2 TO n
        temp ← a + b
        a ← b
        b ← temp
    RETURN b

O(1) space instead of O(n).

Classic Problems

Longest Common Subsequence (LCS)

Find the longest subsequence common to two sequences.

Recurrence:

LCS(i, j) = { LCS(i-1, j-1) + 1           if X[i] == Y[j]
             { max(LCS(i-1, j), LCS(i, j-1)) otherwise

FUNCTION LCS(x, y)
    m ← length(x), n ← length(y)
    dp ← (m+1) x (n+1) table, initialized to 0
    FOR i ← 1 TO m
        FOR j ← 1 TO n
            IF x[i-1] = y[j-1]
                dp[i][j] ← dp[i-1][j-1] + 1
            ELSE
                dp[i][j] ← MAX(dp[i-1][j], dp[i][j-1])
    RETURN dp[m][n]

Time: O(mn). Space: O(mn), reducible to O(min(m,n)) if only the length is needed.

Edit Distance (Levenshtein)

Minimum operations (insert, delete, replace) to transform one string into another.

ED(i, j) = { ED(i-1, j-1)                  if X[i] == Y[j]
            { 1 + min(ED(i-1, j),           (delete from X)
                     ED(i, j-1),            (insert into X)
                     ED(i-1, j-1))          (replace)

Time: O(mn). Used in spell checking, DNA alignment, diff algorithms.

Knapsack

0/1 Knapsack

Items with weight wᵢ and value vᵢ. Knapsack capacity W. Maximize total value.

dp[i][w] = max(dp[i-1][w],                    // don't take item i
               dp[i-1][w - w_i] + v_i)         // take item i (if w_i ≤ w)

Time: O(nW). Space: O(nW), reducible to O(W).

FUNCTION KNAPSACK_01(weights, values, capacity)
    n ← length(weights)
    dp ← array of size capacity + 1, initialized to 0
    FOR i ← 0 TO n - 1
        FOR w ← capacity DOWNTO weights[i]   // reverse to avoid using item twice
            dp[w] ← MAX(dp[w], dp[w - weights[i]] + values[i])
    RETURN dp[capacity]

Unbounded Knapsack

Each item can be used multiple times.

FUNCTION KNAPSACK_UNBOUNDED(weights, values, capacity)
    dp ← array of size capacity + 1, initialized to 0
    FOR w ← 1 TO capacity
        FOR i ← 0 TO length(weights) - 1
            IF weights[i] ≤ w
                dp[w] ← MAX(dp[w], dp[w - weights[i]] + values[i])
    RETURN dp[capacity]

Matrix Chain Multiplication

Parenthesize a sequence of matrices to minimize the number of scalar multiplications.

MCM(i, j) = min over k in [i, j-1] of { MCM(i, k) + MCM(k+1, j) + p_{i-1} × p_k × p_j }

Time: O(n³). Space: O(n²).

Coin Change

Minimum number of coins to make a given amount.

FUNCTION COIN_CHANGE(coins, amount)
    dp ← array of size amount + 1, all set to INFINITY
    dp[0] ← 0
    FOR EACH coin IN coins
        FOR a ← coin TO amount
            IF dp[a - coin] ≠ INFINITY
                dp[a] ← MIN(dp[a], dp[a - coin] + 1)
    IF dp[amount] = INFINITY THEN RETURN -1
    RETURN dp[amount]

Longest Increasing Subsequence (LIS)

Find the longest subsequence where elements are strictly increasing.

O(n²) DP:

dp[i] = 1 + max(dp[j] for j < i where arr[j] < arr[i])

O(n log n) with patience sorting:

Maintain an array tails where tails[i] is the smallest tail element of all increasing subsequences of length i+1.

FUNCTION LIS(arr)
    tails ← empty list
    FOR EACH x IN arr
        pos ← BINARY_SEARCH(tails, x)
        IF x is found in tails
            // do nothing
        ELSE
            IF pos = length(tails)
                APPEND x TO tails
            ELSE
                tails[pos] ← x
    RETURN length(tails)

Advanced DP Techniques

DP on Trees

Process subtrees bottom-up. Each node's DP state depends on its children.

Example: Maximum independent set on a tree. dp[v][0] = max weight not including v. dp[v][1] = max weight including v.

DP on Bitmasks

State includes a bitmask representing a subset of elements.

Example: TSP. dp[mask][i] = minimum cost to visit the set of cities in mask, ending at city i.

// TSP with bitmask DP: O(2^n * n^2)
FUNCTION TSP(dist)
    n ← number of cities
    all ← (1 << n) - 1
    dp ← 2D table of size (2^n) x n, all set to INFINITY
    dp[1][0] ← 0   // start at city 0

    FOR mask ← 1 TO all
        FOR u ← 0 TO n - 1
            IF dp[mask][u] = INFINITY THEN CONTINUE
            FOR v ← 0 TO n - 1
                IF bit v is set in mask THEN CONTINUE
                new_mask ← mask OR (1 << v)
                dp[new_mask][v] ← MIN(dp[new_mask][v], dp[mask][u] + dist[u][v])
    RETURN MIN over i of (dp[all][i] + dist[i][0])

Time: O(2ⁿ × n²). Feasible for n ≤ 20-23.

DP on Digits

Count numbers in a range [L, R] satisfying some property. Process digits from most significant to least, tracking whether we're still "tight" to the bound.

DP Optimization

Knuth's Optimization

For interval DP where the optimal split point is monotone: O(n³) → O(n²).

Divide and Conquer DP

When the recurrence has the monotone property dp[i][j] depends on dp[i-1][k] where optimal k is non-decreasing in j: O(n²k) → O(nk log n).

Convex Hull Trick

Optimize transitions of the form dp[i] = min(dp[j] + f(j) × g(i)) when f and g are monotone. O(n) amortized with a deque.

DP Design Process

  1. Define the state: What information do you need to make a decision? (index, remaining capacity, bitmask, etc.)
  2. Define the recurrence: How does the current state relate to previous states?
  3. Identify base cases: What are the trivial subproblems?
  4. Determine computation order: Bottom-up or top-down? Dependencies determine order.
  5. Analyze time and space: States × transitions per state.
  6. Optimize: Space (rolling array), time (optimization techniques above).

Applications in CS

  • Bioinformatics: Sequence alignment (Smith-Waterman, Needleman-Wunsch = edit distance variants).
  • Natural language processing: CKY parsing, Viterbi algorithm (HMM decoding), beam search.
  • Compilers: Register allocation (optimal code generation for expression trees), instruction scheduling.
  • Networking: Shortest path (Bellman-Ford, Floyd-Warshall). Optimal routing.
  • Operations research: Knapsack, scheduling, inventory management, resource allocation.
  • Computer graphics: Seam carving for content-aware image resizing.
  • Machine learning: Viterbi decoding (CRF), CTC decoding, dynamic time warping.
  • Finance: Option pricing (binomial tree model), portfolio optimization.