Dynamic Programming

Chapter 1: Top-Down Memoization

The recursion tree in Chapter 0 showed the disease: redundant recomputation. Now here is the cure — and it is embarrassingly simple.

Keep the exact same recursive structure. Change nothing about the logic. Just add a table. Before computing r(k), check: "Have I already computed this?" If yes, return the stored answer immediately. If no, compute it, store it in the table, and return it. Done.

This technique is called memoization (not memorization — no 'r'). The word comes from "memo," as in writing yourself a note so you do not forget.

The CLRS Price Table

We will use this price table throughout the lesson. It comes directly from CLRS and is the standard reference example:

Notice something interesting: p₃=8 is less than 2·p₂=10. Two 2-inch pieces ($5+$5=$10) are worth more than one 3-inch piece ($8). This means the "do not cut" option is NOT always optimal. You need to consider all possibilities — which is exactly what the DP does.

Also notice that the prices are not proportional to length. The price-per-inch varies wildly:

If prices grew linearly with length (constant $/inch), the optimal solution would always be "do not cut." The non-linear pricing is what makes the problem interesting and what makes DP necessary. A greedy "always cut at the best $/inch" strategy does not work because it does not account for how the remaining pieces can be cut.

Worked Example: n=4, Every Single Step

We want r(4). The recurrence says try all first cuts i=1,2,3,4:

We need r(3), r(2), r(1), r(0). With memoization, we compute each exactly once. Let us trace the calls in order. The recursive function is called with k=4. It calls r(3) first.

Optimal revenue: $10. Achieved by cutting into two pieces of length 2 ($5 + $5 = $10). The whole rod (length 4) only sells for $9. Two halves beat the whole.

Count the work: we computed r(0), r(1), r(2), r(3), r(4) — five subproblems. For r(k), we tried k values of i. Total comparisons: 0+1+2+3+4 = 10. The naive recursion would have made 2³ = 8 calls, many redundant. For larger n, the savings are astronomical.

The simulation below shows this visually. On the left: the full naive recursion tree (every call executed). On the right: the memoized version where pruned (cached) calls are dimmed gray.

The Code

python
def memoized_rod_cut(p, n):
    """Top-down memoized rod cutting.
    p: list of prices, p[i] = price for length i+1 (0-indexed)
    n: rod length
    Returns: maximum revenue"""
    memo = [-1] * (n + 1)
    memo[0] = 0  # base case: zero-length rod = $0

    def helper(k):
        if memo[k] >= 0:
            return memo[k]  # cache hit — O(1) lookup
        best = 0
        for i in range(1, k + 1):
            best = max(best, p[i - 1] + helper(k - i))
        memo[k] = best  # store for future lookups
        return best

    return helper(n)

# CLRS price table
prices = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
print(memoized_rod_cut(prices, 4))   # 10  (cut: 2+2)
print(memoized_rod_cut(prices, 7))   # 18  (cut: 1+6 or 2+2+3)
print(memoized_rod_cut(prices, 10))  # 30  (don't cut: p[10]=30)

Time complexity: O(n²). There are n+1 subproblems. Each subproblem r(k) iterates over k choices. Total: 0+1+2+...+n = n(n+1)/2 = O(n²).

Space complexity: O(n) for the memo table + O(n) for the recursion call stack (maximum depth is n when the recursive chain is r(n)→r(n-1)→...→r(0)).

Python's Built-in Memoization: @lru_cache

Python has a built-in memoization decorator that makes top-down DP trivially easy:

python
from functools import lru_cache

prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

@lru_cache(maxsize=None)
def rod_cut(n):
    if n == 0: return 0
    return max(prices[i] + rod_cut(n - i) for i in range(1, n + 1))

print(rod_cut(7))  # 18
print(rod_cut.cache_info())
# CacheInfo(hits=21, misses=8, maxsize=None, currsize=8)

@lru_cache(maxsize=None) creates an unlimited-size dictionary cache. The cache_info() method shows cache hit statistics — useful for verifying your DP is actually avoiding recomputation. For interview whiteboard coding, always write the manual memo array version. But for production code and competitive programming, @lru_cache is the standard Python idiom.

Memoization with Multiple State Variables

Some problems have more than one state variable. For example, the 0/1 knapsack has two: item index and remaining capacity. You can memoize with a 2D array or a tuple key:

python
@lru_cache(maxsize=None)
def knapsack_memo(i, w):
    """Top-down memoized 0/1 knapsack.
    i: consider items 0..i
    w: remaining capacity"""
    if i < 0 or w <= 0:
        return 0
    wi, vi = items[i]
    # Skip item i
    skip = knapsack_memo(i - 1, w)
    # Take item i (if it fits)
    take = vi + knapsack_memo(i - 1, w - wi) if wi <= w else 0
    return max(skip, take)

items = [(2,3), (3,4), (4,5), (5,6)]
print(knapsack_memo(len(items)-1, 8))  # 10

The cache key is the tuple (i, w). There are n·W unique keys, so the cache has at most n·W entries. This exactly matches the bottom-up table size.

Chapter 2: Bottom-Up Tabulation

Memoization starts at the top (the problem you want to solve) and works downward, caching along the way. Bottom-up tabulation flips the order: start from the smallest subproblems and build upward. By the time you need r(k), every subproblem r(0), r(1), ..., r(k-1) is already sitting in the table, ready to use.

No recursion. No function call overhead. No stack depth worries. Just a clean, simple for-loop filling a table from left to right.

Think of it this way. Memoization is like exploring a maze and leaving breadcrumbs so you never revisit a dead end. Bottom-up tabulation is like having a map of the entire maze before you start — you fill in the solution for every room, beginning with the ones closest to the exit.

The Algorithm

Worked Example: n=7, Every Cell

Prices: p = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]. We build r[0..7] and s[1..7].

Solution reconstruction: r[7]=18, s[7]=1 means the first cut is at length 1. Remaining length: 7-1=6. s[6]=6 means do not cut the 6-inch piece. Solution: 1+6 = $1+$17 = $18.

But the 4-way tie at j=7 means there are multiple optimal solutions: 1+6, 2+2+3, 3+2+2, 6+1. All yield $18. The s-table just records the first one found.

The Code

python
def bottom_up_rod_cut(p, n):
    """Bottom-up rod cutting with solution reconstruction.
    p: list of prices (0-indexed: p[0] = price for length 1)
    n: rod length
    Returns: (max_revenue, list_of_cut_lengths)"""
    r = [0] * (n + 1)  # r[j] = optimal revenue for rod of length j
    s = [0] * (n + 1)  # s[j] = first piece length in optimal solution for j

    for j in range(1, n + 1):
        best = -1
        for i in range(1, j + 1):
            if p[i - 1] + r[j - i] > best:
                best = p[i - 1] + r[j - i]
                s[j] = i
        r[j] = best

    # Reconstruct the actual cuts
    cuts = []
    remaining = n
    while remaining > 0:
        cuts.append(s[remaining])
        remaining -= s[remaining]

    return r[n], cuts

prices = [1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
revenue, cuts = bottom_up_rod_cut(prices, 7)
print(f"Revenue: ${revenue}, Cuts: {cuts}")
# Revenue: $18, Cuts: [1, 6]

revenue, cuts = bottom_up_rod_cut(prices, 10)
print(f"Revenue: ${revenue}, Cuts: {cuts}")
# Revenue: $30, Cuts: [10]  (don't cut!)

Top-Down vs Bottom-Up Summary

Solution Reconstruction: Following the Bread Crumbs

The s-table (the cut table) is crucial. Without it, you know the OPTIMAL VALUE but not the OPTIMAL SOLUTION. Here is how reconstruction works for rod cutting:

python
# After bottom-up computation, s[j] = length of first piece in optimal solution for rod of length j

def reconstruct_cuts(s, n):
    """Follow the s-table to recover all cuts."""
    cuts = []
    remaining = n
    while remaining > 0:
        first_piece = s[remaining]
        cuts.append(first_piece)
        remaining -= first_piece
        # Now solve the remaining subproblem
    return cuts

# For our example with n=7:
# s = [0, 1, 2, 3, 2, 2, 6, 1]
# reconstruct_cuts(s, 7):
#   remaining=7, s[7]=1, cuts=[1], remaining=6
#   remaining=6, s[6]=6, cuts=[1,6], remaining=0
#   → [1, 6] → revenue = $1 + $17 = $18 ✓

This pattern — maintain a "choice" table during the forward pass, trace it backwards during reconstruction — applies to EVERY DP problem. For knapsack: record which items were taken. For LCS: record which characters matched. For edit distance: record which operation was chosen. The forward pass computes values. The backward pass recovers decisions.

A Common Optimization: Reducing Space

For rod cutting, the full table is already O(n) — there is nothing to optimize. But for 2D problems like knapsack or LCS, the table is O(m×n) and we often only need the previous row. The "rolling row" trick keeps two rows instead of m+1, reducing space dramatically.

The trade-off: with only two rows, you lose the ability to trace back (you no longer have the full table). If you need BOTH the optimal value AND the optimal solution in reduced space, you need Hirschberg's technique — run the DP forward from the start and backward from the end, use the meeting point to divide the problem in half, and recurse. This gives O(min(m,n)) space with O(m·n) time for full reconstruction.

The General Rule for Fill Order

How do you determine the correct fill order for a new DP problem? The rule is simple: every value you READ must have been WRITTEN already.

If you are unsure, draw the dependency arrows for a small example. The fill order is any topological order of those arrows. For most problems, the natural left-to-right / top-to-bottom / small-to-large order works.

Chapter 3: The DP Recipe

You have seen rod cutting solved two ways. Now let us extract the general method. Every dynamic programming solution follows the same four steps. Master this recipe and you can attack any DP problem — even ones you have never seen.

The Four Steps (CLRS Section 15.3)

When Is It DP? The Decision Framework

Not every optimization problem is a DP problem. Two conditions must both hold. The simulation below helps you classify any new problem.

Concrete Example: When Substructure Breaks

Consider this graph with 4 vertices and edges: A-B, B-C, C-D, A-C, B-D.

The problem is that subproblems are NOT independent. The "simple" constraint couples them: using a vertex in one subpath removes it from others. In DP, subproblems must be independent — the solution to one cannot affect the feasibility of another. Shortest paths DO have this property (subpaths of shortest paths are shortest), but longest simple paths do not.

Proving Optimal Substructure: A Template

For interviews, you should be able to prove optimal substructure for any DP problem. The template is always the same. Let us demonstrate with LCS:

The structure is always: (1) assume the whole solution is optimal, (2) suppose a sub-solution is NOT optimal, (3) replace it with the optimal sub-solution, (4) show this improves the whole solution, (5) contradiction. This works for rod cutting (replace non-optimal remainder), knapsack (replace non-optimal sub-selection), edit distance (replace non-optimal sub-alignment), and every other DP problem.

DP vs Divide-and-Conquer vs Greedy

Think of it as a hierarchy. Greedy is the simplest: one choice per step, no table. Divide-and-conquer adds recursion on multiple subproblems. DP adds caching to handle overlap. If greedy works, use it (faster, simpler). If subproblems are independent, use divide-and-conquer. If subproblems overlap, you need DP.

Top-Down vs Bottom-Up: The Detailed Trade-offs

Chapter 4: Matrix-Chain Multiplication

Multiplying two matrices A (p×q) and B (q×r) costs p·q·r scalar multiplications. The result is a p×r matrix. If you have a chain of matrices A₁·A₂·A₃·...·A_n, the order you parenthesize them does not change the result (matrix multiplication is associative) — but it can change the cost by orders of magnitude.

A Dramatic Example

Three matrices: A₁ is 10×30, A₂ is 30×5, A₃ is 5×60.

Same final matrix, but option 1 is 6× cheaper. The difference grows with more matrices. For a chain of n matrices, the number of possible parenthesizations is the (n-1)th Catalan number, which grows as Ω(4ⁿ/n^3/2). Brute-forcing all parenthesizations is not feasible.

Step 1: Optimal Substructure

Suppose the optimal parenthesization of A₁..A_n splits at position k: (A₁..A_k)·(A_k+1..A_n). Then the parenthesization of A₁..A_k within this solution MUST be optimal for A₁..A_k alone. Why? Cut-and-paste: if it were not optimal, replace it with the optimal one and the whole solution improves — contradiction.

Step 2: The Recurrence

Store matrix dimensions in an array p[0..n] where matrix A_i has dimensions p[i-1]×p[i]. Define m[i,j] = minimum number of scalar multiplications to compute A_i·A_i+1·...·A_j.

For each possible split point k, the cost is: (cost of left half) + (cost of right half) + (cost of multiplying the two results). We minimize over all choices of k.

Step 3: Bottom-Up Computation (Diagonal Fill)

Unlike rod cutting (which fills a 1D array left-to-right), matrix chain fills a 2D table diagonally. We compute chains of increasing length: length 1 (base cases on the main diagonal), then length 2, then length 3, and so on. Each entry m[i,j] depends on entries m[i,k] and m[k+1,j] for k in [i,j) — all of which are shorter chains, hence already computed.

Worked Example: 4 Matrices

A₁(30×35), A₂(35×15), A₃(15×5), A₄(5×10). Dimensions array: p = [30, 35, 15, 5, 10].

Optimal parenthesization: split at k=3 means ((A₁..A₃) · A₄). For A₁..A₃, split at k=1 means (A₁ · (A₂·A₃)). Full: ((A₁·(A₂·A₃))·A₄), cost 9375.

python
def matrix_chain_order(p):
    """Find optimal parenthesization for matrix chain.
    p: list of dimensions [p0, p1, ..., pn] where Ai is p[i-1] x p[i]
    Returns: (m, s) — cost table and split table"""
    n = len(p) - 1  # number of matrices
    m = [[0] * (n + 1) for _ in range(n + 1)]
    s = [[0] * (n + 1) for _ in range(n + 1)]

    for L in range(2, n + 1):  # L = chain length
        for i in range(1, n - L + 2):
            j = i + L - 1
            m[i][j] = float('inf')
            for k in range(i, j):  # try all split points
                cost = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if cost < m[i][j]:
                    m[i][j] = cost
                    s[i][j] = k
    return m, s

def print_parens(s, i, j):
    """Reconstruct optimal parenthesization."""
    if i == j: return f"A{i}"
    k = s[i][j]
    left = print_parens(s, i, k)
    right = print_parens(s, k + 1, j)
    return f"({left} x {right})"

p = [30, 35, 15, 5, 10]
m, s = matrix_chain_order(p)
print(f"Min cost: {m[1][4]}")    # 9375
print(print_parens(s, 1, 4))  # ((A1 x (A2 x A3)) x A4)

Time complexity: O(n³). Three nested loops — chain length L (n iterations), start index i (up to n), split point k (up to n). Space: O(n²) for the two n×n tables.

Understanding the Three Nested Loops

The triple loop in matrix chain is the most confusing part for beginners. Let us break it down with concrete numbers for n=4 matrices:

The key insight: L controls which diagonal of the table we fill. Within each diagonal, i controls which cell. Within each cell, k controls which split we try. Every split references entries from shorter diagonals (already filled). This is why the order works.

Common Interview Variant: Minimum Cost to Merge Stones

Matrix chain has many disguises in interviews. One common one: "Given n piles of stones with sizes a[1]..a[n], merge adjacent piles. The cost of merging two adjacent piles is their combined size. Find the minimum total cost to merge all piles into one."

This is EXACTLY matrix chain with a different cost function. The subproblem m[i,j] = minimum cost to merge piles i through j. The split point k divides into (merge i..k) + (merge k+1..j) + (cost of combining the two result piles = sum of a[i] through a[j]). Same O(n³) DP.

Chapter 5: Longest Common Subsequence

Given two strings, find the longest subsequence common to both. A subsequence is formed by deleting zero or more characters from a string WITHOUT changing the order of the remaining characters. It is NOT the same as a substring (which must be contiguous characters).

Example: X = "ABCBDAB", Y = "BDCAB". One common subsequence is "BCAB" (length 4). Another is "BDA" (length 3). The longest common subsequence (LCS) has length 4. Finding it by brute force means checking all 2^m subsequences of X against all 2ⁿ subsequences of Y — exponential in both dimensions.

Why LCS Matters

LCS is everywhere in real software:

Step 1: Characterize Optimal Substructure

Let X = x₁x₂...x_m and Y = y₁y₂...y_n. Let Z = z₁z₂...z_k be any LCS of X and Y. Three cases:

In every case, the LCS of the full strings contains the LCS of shorter strings. Optimal substructure holds.

Step 2: The Recurrence

Define c[i,j] = length of the LCS of X[1..i] and Y[1..j].

Worked Example: "ABCBDAB" vs "BDCAB"

Let us fill the entire 8×6 table:

LCS length = c[7,5] = 4. Traceback from c[7,5]: x₇=B=y₅ (match, go diagonal). c[6,4]: x₆=A=y₄ (match, go diagonal). c[5,3]: x₅=D≠C, c[4,3]=2≥c[5,2]=1, go up. c[4,3]: x₄=B≠C, c[3,3]=2≥c[4,2]=1, go up. c[3,3]: x₃=C=y₃ (match, go diagonal). c[2,2]: x₂=B≠D, c[1,2]=0<c[2,1]=1, go left. c[2,1]: x₂=B=y₁ (match, go diagonal). c[1,0]=0, stop.

Matches collected (in reverse): B, A, C, B → LCS = "BCAB".

python
def lcs(X, Y):
    """Compute LCS length and string with traceback."""
    m, n = len(X), len(Y)
    c = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1  # match
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    # Traceback to reconstruct the LCS
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            result.append(X[i-1])
            i -= 1; j -= 1  # go diagonal
        elif c[i-1][j] >= c[i][j-1]:
            i -= 1  # go up
        else:
            j -= 1  # go left

    return c[m][n], ''.join(reversed(result))

length, subseq = lcs("ABCBDAB", "BDCAB")
print(f"LCS length: {length}, LCS: {subseq}")
# LCS length: 4, LCS: BCAB

Time: O(m·n). Space: O(m·n) for the full table. Can be reduced to O(min(m,n)) if you only need the LENGTH (keep only two rows), but then you lose the ability to reconstruct the actual LCS. For traceback in O(min(m,n)) space, use Hirschberg's algorithm — a divide-and-conquer trick that runs the LCS forward and backward to find the midpoint of the LCS in linear space.

How diff Uses LCS

The Unix diff utility compares two files line by line. It treats each LINE as a single "character" and computes the LCS of the two line sequences. Lines in the LCS are "unchanged." Lines not in the LCS of the old file are "deleted." Lines not in the LCS of the new file are "inserted."

Real diff implementations use the Myers diff algorithm, which finds the shortest edit script in O((m+n)·D) time where D is the edit distance. For similar files (small D), this is much faster than O(m·n). But the core idea is still LCS.

Space-Optimized LCS (Length Only)

python
def lcs_length_only(X, Y):
    """O(min(m,n)) space LCS — returns length only, no traceback."""
    if len(X) < len(Y):
        X, Y = Y, X  # iterate over shorter string for space savings
    n = len(Y)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, len(X) + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0] * (n + 1)

    return prev[n]

print(lcs_length_only("ABCBDAB", "BDCAB"))  # 4

Finding ALL LCS (Multiple Optimal Solutions)

The LCS is not always unique. "ABCBDAB" and "BDCAB" have multiple LCSs of length 4: "BCAB" and "BDAB." When ties occur in the max(c[i-1][j], c[i][j-1]) step, both branches lead to valid LCSs. To enumerate all of them:

python
def all_lcs(X, Y):
    """Find ALL longest common subsequences."""
    m, n = len(X), len(Y)
    c = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    def backtrack(i, j):
        if i == 0 or j == 0:
            return {""}
        if X[i-1] == Y[j-1]:
            return {s + X[i-1] for s in backtrack(i-1, j-1)}
        results = set()
        if c[i-1][j] >= c[i][j-1]:
            results |= backtrack(i-1, j)
        if c[i][j-1] >= c[i-1][j]:
            results |= backtrack(i, j-1)
        return results

    return backtrack(m, n)

print(all_lcs("ABCBDAB", "BDCAB"))
# {'BCAB', 'BDAB'}

The number of distinct LCSs can be exponential in the worst case. This backtracking is only practical for small inputs or when you know the number of solutions is manageable.

LCS Variants in Interviews

Chapter 6: The DP Showcase

Time to put everything together. This is the big interactive simulation — a multi-problem DP solver that lets you watch three classic algorithms work step by step, with full control over speed and parameters.

0/1 Knapsack — The King of DP Problems

Given n items, each with weight w_i and value v_i, and a knapsack with capacity W. Maximize total value without exceeding W. Each item is included whole or not at all — no fractions (hence "0/1").

Subproblem: dp[i][w] = maximum value achievable using items 1..i with knapsack capacity w.

In words: for each item, choose the better of (1) skipping it (keep dp[i-1][w] — best value without this item at this capacity) or (2) taking it (its value v_i plus the best value for the remaining capacity w-w_i without this item, which is dp[i-1][w-w_i]).

Time: O(n·W). Space: O(n·W), reducible to O(W) with a single-row optimization. To do the single-row trick: iterate w from W DOWN to w_i (backwards!) so you do not accidentally use the current row's values (which would allow taking the same item twice).

Knapsack Worked Example

Items: (weight=2, value=3), (weight=3, value=4), (weight=4, value=5), (weight=5, value=6). Knapsack capacity W=8.

Answer: maximum value = $10. Achieved by taking items 2 (w=3,v=4) and 4 (w=5,v=6), total weight=8=W exactly.

python
def knapsack_01(items, W):
    """0/1 Knapsack with solution reconstruction.
    items: list of (weight, value) tuples
    W: knapsack capacity
    Returns: (max_value, selected_items)"""
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        wi, vi = items[i - 1]
        for w in range(W + 1):
            if wi <= w:
                dp[i][w] = max(dp[i-1][w], vi + dp[i-1][w-wi])
            else:
                dp[i][w] = dp[i-1][w]

    # Reconstruct: trace back to find which items were taken
    selected = []
    w = W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i-1][w]:  # item i was taken
            selected.append(i)
            w -= items[i-1][0]

    return dp[n][W], selected[::-1]

items = [(2,3), (3,4), (4,5), (5,6)]
val, sel = knapsack_01(items, 8)
print(f"Max value: {val}, Items: {sel}")
# Max value: 10, Items: [2, 4]

The Space Optimization: Rolling Row

Since dp[i] only depends on dp[i-1], we can keep just two rows (or even one row with a backwards loop):

python
def knapsack_01_optimized(items, W):
    """O(W) space knapsack — single row, backwards iteration."""
    dp = [0] * (W + 1)
    for wi, vi in items:
        # CRITICAL: iterate backwards to avoid using current-row values
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], vi + dp[w - wi])
    return dp[W]

print(knapsack_01_optimized([(2,3), (3,4), (4,5), (5,6)], 8))
# 10

Coin Change — Minimum Coins

Given coin denominations d₁, d₂, ..., d_k and a target amount A, find the minimum number of coins needed. Unlimited supply of each denomination.

For each amount a from 1 to A, try subtracting each coin denomination. The one that leads to the fewest remaining coins wins. If no coin fits, dp[a] = ∞ (impossible).

Time: O(A·k) where k is the number of denominations. Space: O(A).

Coin Change Worked Example

Coins: [1, 3, 4]. Target amount: 6.

Minimum coins for amount 6 = 2 (using two 3-cent coins). Notice the greedy approach (always use the largest coin first) would give {4,1,1} = 3 coins — greedy fails! This is why coin change needs DP.

python
def coin_change(coins, amount):
    """Minimum number of coins to make amount."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    parent = [-1] * (amount + 1)  # for reconstruction

    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                parent[a] = c  # record which coin was used

    # Reconstruct the coins used
    if dp[amount] == float('inf'):
        return -1, []
    used = []
    a = amount
    while a > 0:
        used.append(parent[a])
        a -= parent[a]
    return dp[amount], used

count, coins_used = coin_change([1, 3, 4], 6)
print(f"Min coins: {count}, Used: {coins_used}")
# Min coins: 2, Used: [3, 3]

Longest Increasing Subsequence (LIS)

Given an array of numbers, find the longest strictly increasing subsequence. For [10, 9, 2, 5, 3, 7, 101, 18], the LIS is [2, 3, 7, 101] or [2, 5, 7, 101] — both have length 4.

For each element i, find the longest increasing subsequence ENDING at i by checking all previous elements j where a[j] < a[i]. The overall LIS is max(dp[0], dp[1], ..., dp[n-1]).

LIS Worked Example

Array: [10, 9, 2, 5, 3, 7, 101, 18].

python
def lis_dp(arr):
    """O(n^2) LIS with reconstruction."""
    n = len(arr)
    dp = [1] * n
    parent = [-1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j

    # Find the index with max dp value
    best_idx = dp.index(max(dp))
    # Trace back
    result = []
    idx = best_idx
    while idx != -1:
        result.append(arr[idx])
        idx = parent[idx]
    return max(dp), result[::-1]

length, seq = lis_dp([10, 9, 2, 5, 3, 7, 101, 18])
print(f"LIS length: {length}, LIS: {seq}")
# LIS length: 4, LIS: [2, 5, 7, 101]

Time: O(n²) for the DP approach. Can be improved to O(n log n) with patience sorting — maintain a "tails" array where tails[k] is the smallest tail element of any increasing subsequence of length k+1. For each new element, binary search for its position in the tails array. This is the preferred interview solution for large inputs.

python
import bisect

def lis_binary(arr):
    """O(n log n) LIS using patience sorting."""
    tails = []
    for x in arr:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)  # extend the longest sequence
        else:
            tails[pos] = x   # improve an existing sequence
    return len(tails)

print(lis_binary([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

How to Approach DP Problems in Interviews

Here is a step-by-step template that works for virtually every DP interview question:

Subset Sum: A Building Block

Given a set of positive integers, is there a subset that sums to a target T? This is the boolean version of knapsack and appears constantly as a sub-problem in harder DP problems.

python
def subset_sum(nums, target):
    """Can a subset of nums sum to target?"""
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        # Iterate backwards (0/1 knapsack pattern)
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]
    return dp[target]

print(subset_sum([3, 34, 4, 12, 5, 2], 9))   # True (4+5 or 3+4+2)
print(subset_sum([3, 34, 4, 12, 5, 2], 30))  # False

Subset sum is used as a subroutine in "Partition Equal Subset Sum" (can you split an array into two subsets with equal sum? — just check if a subset sums to total/2) and "Target Sum" (assign + or - to each number to hit a target).

Climbing Stairs with Variable Step Sizes

The classic climbing stairs (1 or 2 steps) is just Fibonacci. But with variable step sizes [1, 3, 5], it becomes coin change without the "minimize" — just count the ways:

python
def climb_stairs(n, steps):
    """Number of ways to climb n stairs with given step sizes."""
    dp = [0] * (n + 1)
    dp[0] = 1  # one way to stay at ground: do nothing
    for i in range(1, n + 1):
        for s in steps:
            if i >= s:
                dp[i] += dp[i - s]
    return dp[n]

print(climb_stairs(4, [1, 2]))      # 5 (Fibonacci!)
print(climb_stairs(10, [1, 3, 5]))  # 47

Debugging DP in Interviews

If your DP gives wrong answers during an interview, here is the 30-second diagnostic checklist:

Chapter 7: Edit Distance

How many single-character operations does it take to transform one string into another? This question has a name — the edit distance (also called Levenshtein distance) — and it is one of the most practical DP problems in all of computer science. Your spell checker uses it. Your diff tool uses it. DNA alignment tools use a weighted version of it. Even fuzzy search engines like Elasticsearch use it under the hood.

The three allowed operations, each costing 1:

A Worked Transformation

Transform "kitten" into "sitting":

But how do we know 3 is optimal? Maybe there is a way to do it in 2 operations? The DP table proves no shorter sequence of operations exists.

The Recurrence

Define d[i,j] = edit distance between X[1..i] and Y[1..j].

The [x_i ≠ y_j] notation means: cost 0 if the characters match (no operation needed), cost 1 if they differ (replace). A match is essentially a "free diagonal step."

Full Table: "kitten" → "sitting"

d[6,7] = 3. Three operations needed. Let us verify this is optimal by considering alternatives:

Let us trace back through the table to find the exact operations:

The key operations are: replace 'k'→'s', match i,t,t, replace 'e'→'i', match n, insert 'g'. Total non-free operations: 3.

Applications in the Real World

python
def edit_distance(X, Y):
    """Compute Levenshtein distance between two strings."""
    m, n = len(X), len(Y)
    d = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases: transforming to/from empty string
    for i in range(m + 1): d[i][0] = i
    for j in range(n + 1): d[0][j] = j

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if X[i-1] == Y[j-1] else 1
            d[i][j] = min(
                d[i-1][j] + 1,      # delete x_i
                d[i][j-1] + 1,      # insert y_j
                d[i-1][j-1] + cost  # replace (or free match)
            )

    return d[m][n]

print(edit_distance("kitten", "sitting"))   # 3
print(edit_distance("sunday", "saturday"))  # 3
print(edit_distance("horse", "ros"))       # 3

Time: O(m·n). Space: O(m·n), reducible to O(min(m,n)) since each row only depends on the previous row.

Variants and Weighted Edit Distance

The standard Levenshtein distance treats all operations as cost 1. But in practice, costs are often weighted:

The DP approach handles all weighted variants — just change the costs in the min() computation. The structure of the table and traceback remain identical.

Edit Distance: The Full Traceback

Knowing the distance is useful, but often you need the ACTUAL sequence of operations. Here is the complete code with operation reconstruction:

python
def edit_distance_with_ops(X, Y):
    """Edit distance with full operation traceback."""
    m, n = len(X), len(Y)
    d = [[0] * (n + 1) for _ in range(m + 1)]
    ops = [[''] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        d[i][0] = i
        ops[i][0] = 'D'  # delete
    for j in range(n + 1):
        d[0][j] = j
        ops[0][j] = 'I'  # insert
    ops[0][0] = ''

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:
                d[i][j] = d[i-1][j-1]
                ops[i][j] = 'M'  # match (free)
            else:
                choices = [
                    (d[i-1][j] + 1, 'D'),   # delete x_i
                    (d[i][j-1] + 1, 'I'),   # insert y_j
                    (d[i-1][j-1] + 1, 'R')  # replace
                ]
                d[i][j], ops[i][j] = min(choices)

    # Trace back to find operations
    result = []
    i, j = m, n
    while i > 0 or j > 0:
        op = ops[i][j]
        if op == 'M':
            result.append(f"match '{X[i-1]}'")
            i -= 1; j -= 1
        elif op == 'R':
            result.append(f"replace '{X[i-1]}' with '{Y[j-1]}'")
            i -= 1; j -= 1
        elif op == 'D':
            result.append(f"delete '{X[i-1]}'")
            i -= 1
        elif op == 'I':
            result.append(f"insert '{Y[j-1]}'")
            j -= 1

    return d[m][n], result[::-1]

dist, operations = edit_distance_with_ops("kitten", "sitting")
print(f"Distance: {dist}")
for op in operations:
    print(f"  {op}")
# Distance: 3
#   replace 'k' with 's'
#   match 'i'
#   match 't'
#   match 't'
#   replace 'e' with 'i'
#   match 'n'
#   insert 'g'

Second Worked Example: "horse" → "ros"

This is a popular LeetCode problem (LC #72). Let us trace it completely:

d[5,3] = 3. Operations: replace 'h'→'r', match 'o', delete 'r', match 's', delete 'e'. But wait, a simpler reading: delete 'h', match 'o'... let us trace properly from d[5,3]=3. d[5,3] came from d[4,2]+1=3+... Actually the min of d[4,3]+1=3, d[5,2]+1=5, d[4,2]+[e≠s]=3+1=4. So d[5,3]=3 via delete. d[4,3]=2 via d[3,2]+[s=s]=2+0=2, match. d[3,2]=2 via d[2,2]+1=2 (delete r), or d[2,1]+1=3, or d[2,1]+[r≠o]=... d[3,2] came from d[2,1]+[r≠o]=2+1=3, d[3,1]+1=3, d[2,2]+1=2. Via delete. d[2,2]=1 via d[1,1]+[o=o? no, o≠r]=1+1=2, or d[1,2]+1=3, or d[2,1]+1=3. Wait, d[2,2]: x₂='o', y₂='o', match! d[1,1]+0=1. So d[2,2]=1 via match. d[1,1]=1 via d[0,0]+[h≠r]=0+1=1, replace. Operations: replace h→r, match o, delete r, match s, delete e. 3 operations confirmed.

Space Optimization for Edit Distance

Since each row d[i] only depends on d[i-1], we can use two rows instead of m+1 rows, reducing space from O(m·n) to O(n). This is critical when comparing long sequences (e.g., DNA with millions of base pairs):

python
def edit_distance_space_opt(X, Y):
    """O(min(m,n)) space edit distance."""
    if len(X) < len(Y):
        X, Y = Y, X  # ensure Y is shorter (iterate over shorter dimension)
    m, n = len(X), len(Y)
    prev = list(range(n + 1))  # previous row
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        curr[0] = i
        for j in range(1, n + 1):
            cost = 0 if X[i-1] == Y[j-1] else 1
            curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + cost)
        prev, curr = curr, prev  # swap rows

    return prev[n]

print(edit_distance_space_opt("kitten", "sitting"))  # 3

Bonus: Wildcard Matching (LeetCode #44)

A closely related problem: given a string s and a pattern p with '?' (matches any single character) and '*' (matches any sequence including empty), determine if s matches p. This is string DP disguised as pattern matching.

python
def wildcard_match(s, p):
    """Wildcard pattern matching: ? = any char, * = any sequence."""
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    # Handle leading *s in pattern
    for j in range(1, n + 1):
        if p[j-1] == '*': dp[0][j] = dp[0][j-1]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            elif p[j-1] == '?' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]

    return dp[m][n]

print(wildcard_match("adceb", "*a*b"))     # True
print(wildcard_match("acdcb", "a*c?b"))    # False

The '*' case is the tricky one. dp[i][j-1] means '*' matches empty (skip it). dp[i-1][j] means '*' matches s[i] and potentially more characters (the '*' stays active). This is elegant because it naturally handles '*' matching any number of characters through the chain of dp[i-1][j] ← dp[i-2][j] ← ... lookups.

Chapter 8: DP on Trees and DAGs

So far, every DP problem has used a 1D array or a 2D table. But dynamic programming is far more general than that. It works on ANY structure whose dependency graph is a DAG (directed acyclic graph). Trees are the most natural example: the value at a node depends only on the values of its children.

Optimal Binary Search Tree (CLRS 15.5)

You are building a binary search tree for a fixed set of keys k₁ < k₂ < ... < k_n. Each key has a known search probability p_i (how often it is searched for). You want the BST that minimizes the expected search cost: the sum of (depth + 1) × p_i for each key.

If all keys are equally likely, a balanced BST is optimal. But when probabilities are skewed, you want frequently-accessed keys near the root, even at the cost of pushing rare keys deeper. This is exactly how Huffman coding works for prefix codes, but for BSTs the constraint is different: the search-tree property must hold.

The subproblem is identical in structure to matrix-chain multiplication. Define e[i,j] = minimum expected search cost for a BST containing keys k_i..k_j. Try each key k_r (i ≤ r ≤ j) as the root.

Why Not Just Use a Balanced BST?

Consider keys {A, B, C} with search probabilities p_A=0.7, p_B=0.2, p_C=0.1. A balanced BST puts B at the root (depth 1), A left (depth 2), C right (depth 2). Expected cost = 0.7×2 + 0.2×1 + 0.1×2 = 1.8.

But putting A at the root (depth 1), B right (depth 2), C right-right (depth 3): cost = 0.7×1 + 0.2×2 + 0.1×3 = 1.4. Much better! The most frequently accessed key should be near the root, even at the cost of making the tree unbalanced.

Finding the optimal arrangement is the optimal BST problem:

where w(i,j) = p_i + p_i+1 + ... + p_j is the sum of frequencies in the range. The w(i,j) term arises because every node in the subtree drops one level when placed under root r, adding its probability to the cost. Time: O(n³), Space: O(n²).

Tree DP: Maximum Weight Independent Set

This is the classic "company party" problem. A company has a tree-shaped hierarchy (each employee has exactly one direct boss, except the CEO at the root). Each employee has a "fun rating." You want to invite a subset of employees to a party that maximizes the total fun, subject to one rule: no employee can attend if their direct boss also attends.

This is an independent set problem on a tree (NP-hard on general graphs, but polynomial on trees thanks to DP!).

For each node v, define two values:

Process bottom-up via post-order traversal. Leaves first, then their parents, up to the root. For leaf nodes: include[leaf] = fun[leaf], exclude[leaf] = 0. The answer for the whole company is max(include[root], exclude[root]).

python
class TreeNode:
    def __init__(self, val, children=None):
        self.val = val
        self.children = children or []

def max_independent_set(root):
    """Maximum weight independent set on a tree.
    Returns: (max_value, set_of_selected_nodes)"""

    def dp(node):
        """Returns (include_value, exclude_value)"""
        if not node.children:
            return node.val, 0  # leaf: include=val, exclude=0

        incl = node.val
        excl = 0
        for child in node.children:
            c_incl, c_excl = dp(child)
            incl += c_excl  # if we include node, must exclude children
            excl += max(c_incl, c_excl)  # if we exclude node, children are free
        return incl, excl

    incl, excl = dp(root)
    return max(incl, excl)

# Build the example tree from the diagram
tree = TreeNode(8, [
    TreeNode(3, [TreeNode(7), TreeNode(2, [TreeNode(5)])]),
    TreeNode(4, [TreeNode(6), TreeNode(1)])
])
print(max_independent_set(tree))  # 27

The time complexity of this DFS is O(n) — each node is visited exactly once. The space is O(n) for the recursion stack (O(h) where h is tree height, worst case O(n) for a skewed tree).

This same pattern — define include[v] and exclude[v] for each node, compute via post-order DFS — solves many tree DP problems:

Longest Path in a DAG

The longest path problem is NP-hard on general graphs (it subsumes the Hamiltonian path problem). But on a DAG, it is solvable in O(V+E) time using DP over a topological sort.

Process vertices in topological order. For each vertex v, look at all incoming edges and take the maximum. This is fundamentally DP: the "table" is indexed by vertices, the "fill order" is topological order, and each vertex depends only on its predecessors.

The Subproblem DAGs for Our Problems

This DAG perspective explains WHY the DP works: we are simply computing values in topological order on the dependency graph. It also explains WHY circular dependencies are forbidden: a cycle in the DAG would mean a subproblem depends on itself, which is undefined.

DP on DAGs: Concrete Example

Consider a DAG with vertices A, B, C, D, E and weighted edges A→B(3), A→C(6), B→D(4), B→E(1), C→D(2), C→E(7), D→E(5). The longest path from A to E:

This is exactly the same as any other DP: define state (vertex), write recurrence (max over incoming edges), fill in topological order. The only difference is the "table" is indexed by graph vertices instead of integers or pairs.

Worked Example: Tree DP by Hand

Consider this tree (node values in parentheses):

Post-order traversal visits: 7, 5, 2, 3, 6, 1, 4, 8.

Time complexity of tree DP: O(n) where n is the number of nodes. Each node is visited exactly once in post-order, and the work at each node is proportional to its number of children. The sum of children counts over all nodes is n-1 (a tree with n nodes has n-1 edges). So total work is O(n).

Chapter 9: Interview Arsenal

This is your reference sheet. Every classic DP problem, categorized by structure, with recurrence, complexity, and interview framing. Print this. Memorize it. Use it.

The Six DP Categories

Complete Cheat Sheet

The Four Interview Patterns

Debug Checklist: "My DP Gives Wrong Answers"

System Design: DP in Production

"Design an autocomplete with fuzzy matching."

Use edit distance with a BK-tree (ball tree for metric spaces). Index all dictionary words. Given a query, traverse the tree, pruning branches where the triangle inequality guarantees distance exceeds threshold. Reduces O(n) distance computations to O(n^0.6) average. For real-time autocomplete, precompute all words within distance 1 and 2 of common prefixes.

"Design a recommendation engine using sequence alignment."

Model user behavior as a sequence of actions (viewed product A, searched for B, purchased C). Compute an LCS-variant similarity between users: users with similar action subsequences get similar recommendations. Use the O(min(m,n)) space optimization since you only need the similarity score, not the full alignment.

Buy and Sell Stock: State Machine DP

This family of problems is a favorite at FAANG interviews. The simplest version: given an array of stock prices, find the maximum profit from at most one buy-sell transaction.

For "at most k transactions," add a transaction counter dimension: dp[i][k][state]. For "with cooldown," add a "just_sold" state that prevents buying the next day. The state machine pattern handles all variants.

python
def max_profit(prices):
    """Best Time to Buy and Sell Stock (single transaction)."""
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit

def max_profit_k(prices, k):
    """Best Time to Buy and Sell Stock with at most k transactions."""
    n = len(prices)
    if k >= n // 2:  # unlimited transactions
        return sum(max(0, prices[i+1]-prices[i]) for i in range(n-1))
    dp = [[0] * n for _ in range(k + 1)]
    for t in range(1, k + 1):
        max_prev = -prices[0]
        for j in range(1, n):
            dp[t][j] = max(dp[t][j-1], prices[j] + max_prev)
            max_prev = max(max_prev, dp[t-1][j] - prices[j])
    return dp[k][n-1]

print(max_profit([7,1,5,3,6,4]))  # 5 (buy at 1, sell at 6)
print(max_profit_k([3,2,6,5,0,3], 2))  # 7 (buy 2 sell 6, buy 0 sell 3)

House Robber: The Simplest DP

A row of houses, each with a value. Rob houses to maximize total value, but you cannot rob two adjacent houses (alarm will trigger). This is the simplest interesting DP problem and a great warm-up:

Skip house i (take dp[i-1]) or rob house i (take dp[i-2] + value[i], since we skip i-1). Only need the last two values, so O(1) space.

python
def rob(nums):
    """House Robber — O(n) time, O(1) space."""
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

print(rob([2,7,9,3,1]))  # 12 (rob houses 1,3: 7+9=... wait, 2+9+1=12)

Word Break: A Practical DP Problem

Given a string s and a dictionary of words, determine if s can be segmented into space-separated dictionary words. "leetcode" with dictionary ["leet", "code"] returns True.

python
def word_break(s, wordDict):
    """Can string s be segmented into dictionary words?"""
    words = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string is valid

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break  # found one valid segmentation, enough

    return dp[n]

print(word_break("leetcode", ["leet", "code"]))     # True
print(word_break("applepenapple", ["apple", "pen"])) # True
print(word_break("catsandog", ["cats","dog","sand","and","cat"]))  # False

Time: O(n²) if word lookups are O(1) (hash set). Space: O(n). This is a 1D DP where dp[i] depends on all dp[j] for j < i — similar to LIS but with a string condition instead of a numerical comparison.

Unique Paths: 2D Grid DP

A robot on an m×n grid starts at top-left and can only move right or down. How many unique paths to the bottom-right? This is the simplest 2D DP and a great warm-up problem.

python
def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

print(unique_paths(3, 7))  # 28
print(unique_paths(3, 3))  # 6

Fun fact: the answer is the binomial coefficient C(m+n-2, m-1), computable in O(min(m,n)) without any DP. But the DP approach generalizes to grids with obstacles (set dp[i][j]=0 for obstacle cells), which the closed-form cannot handle.

Minimum Path Sum: Adding Weights to the Grid

Same grid, but each cell has a cost. Find the path from top-left to bottom-right that minimizes the total cost. Same recurrence, just replace addition with min:

python
def min_path_sum(grid):
    """Minimum cost path from top-left to bottom-right."""
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

print(min_path_sum([[1,3,1],[1,5,1],[4,2,1]]))  # 7 (1→3→1→1→1)

This is one of the cleanest interview problems because the 2D DP is so intuitive. Common follow-up: "What if you can move up, down, left, and right?" Then it is no longer DP (cycles are possible) — you need Dijkstra's algorithm.

Recognizing DP in Disguise

Many interview problems do not say "use DP." You have to recognize the pattern. Here are the tells:

Chapter 10: Connections

Dynamic programming is not an isolated technique. It sits at the center of a web of algorithmic ideas. Understanding where DP ends and other paradigms begin makes you a fundamentally better problem solver.

DP vs Everything Else — The Complete Map

DP in Machine Learning

If you are studying ML (which, given this site, you probably are), DP is everywhere:

Where to Go Next

CLRS Chapter 16: Greedy Algorithms. When DP is overkill. Activity selection, Huffman coding, and fractional knapsack are all solvable with a single greedy pass because the "greedy choice property" holds — you never need to revisit a decision. The contrast with 0/1 knapsack (which requires DP because greedy fails) is the most important dichotomy in algorithm design.

CLRS Chapter 4: Divide-and-Conquer. Merge sort and Strassen's matrix multiplication have optimal substructure but NO overlapping subproblems. The subproblems at each recursion level are always fresh partitions of the input. Memoization would not help because no subproblem is ever repeated. This is why divide-and-conquer leads to recurrence relations (solved by the master theorem), while DP leads to tables.

Graph algorithms. Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall) are all DP in disguise.

Floyd-Warshall: DP on Graphs

Floyd-Warshall computes all-pairs shortest paths in O(V³) time. The DP formulation:

The subproblem d^(k)[i][j] = shortest path from i to j using only vertices {1, 2, ..., k} as intermediates. At each step, we decide: does the shortest path from i to j go through vertex k (use it as a waypoint) or not?

This is structurally identical to 0/1 knapsack! Instead of "take or skip item k," it is "route through vertex k or not." The three nested loops (k, i, j) fill a 3D table, optimized to 2D because d^(k) only depends on d^(k-1). Note the k loop MUST be the outermost loop — this is a common interview trick question.

Why k must be outermost: d[i][j] at stage k needs d[i][k] and d[k][j] from stage k-1. If k were an inner loop, you would mix stages, using some values from the current k and others from a previous k. The outermost position ensures all d values are consistent within each stage.

python
def floyd_warshall(graph):
    """All-pairs shortest paths. graph[i][j] = edge weight (inf if no edge)."""
    n = len(graph)
    d = [row[:] for row in graph]  # copy
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    return d

Bellman-Ford: DP on Edge Count

Bellman-Ford computes single-source shortest paths, even with negative edge weights. The DP interpretation: d^(k)[v] = shortest path from source s to v using at most k edges.

Run for k=1 to V-1 (since a shortest path in a graph with V vertices uses at most V-1 edges). This is bottom-up DP where the "subproblem size" is the number of edges allowed.

The DP Family Tree

Here is how all the problems in this lesson connect to each other and to the broader algorithm landscape:

DP in Competitive Programming

In competitive programming, DP problems are categorized by difficulty:

For coding interviews, medium is the ceiling. You will almost never see bitmask DP or DP with advanced optimizations. Master the basics: 1D, 2D, and interval DP.

A Note on Practice

DP is one of those topics where reading about it is necessary but not sufficient. You need to solve problems. Here is a recommended progression:

After 6 weeks of daily practice (1-2 problems per day), you will recognize DP patterns instantly. The key is not memorizing solutions but understanding WHY each recurrence has the form it does. If you can derive the recurrence from the problem statement, you can solve any DP problem.

Closing Thoughts

CLRS Chapter 15 is arguably the most interview-relevant chapter in the entire book. Every concept here — optimal substructure, overlapping subproblems, the 4-step recipe, memoization vs tabulation, solution reconstruction — appears in real interviews at every major tech company. The specific problems (rod cutting, matrix chain, LCS, optimal BST) are less important than the TECHNIQUE. Once you internalize the technique, you can solve problems you have never seen before.

As Bellman himself wrote in his autobiography: "I decided to use the word 'programming' to describe my work. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying... It's impossible to use the word 'dynamic' in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible."

The name stuck. And 70 years later, dynamic programming remains one of the most powerful tools in every programmer's arsenal — from coding interviews to cutting-edge AI research. Master it, and you will see optimization problems differently forever.

The Limits of DP

DP is powerful but not universal. Here is when it does NOT work:

DP as a Mindset

The real value of studying CLRS Chapter 15 is not memorizing the rod cutting formula or the LCS table. It is learning to think in subproblems. Every time you face an optimization problem, ask yourself:

If you can answer these three questions, you can solve any DP problem. The rest is implementation.

Summary: Key Results from This Lesson

Every one of these speedups comes from the same insight: solve each subproblem once, store the result, look it up next time. The table size is the number of unique subproblems. The fill time is the number of subproblems times the work per subproblem. Everything else is details.

The gap between exponential and polynomial is not academic. For n=50, 2ⁿ ≈ 10¹⁵ operations would take a modern computer about 11 days at 10⁹ ops/sec. n² = 2500 operations takes microseconds. For n=100, the exponential version would outlast the heat death of the universe. The DP version finishes before your IDE can refresh. Dynamic programming does not just make things faster — it makes impossible problems trivial.

That is the power of thinking in subproblems. And that is what CLRS Chapter 15 teaches.