Dynamic Programming

13.1Why dynamic programming?

A DP solution is a dependency graph of states. The recurrence specifies the incoming dependencies; memoization or tabulation determines how the graph is evaluated. Correctness comes from showing that the recurrence covers every valid possibility and combines already-correct smaller answers.

13.2Fibonacci: recursion versus DP

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1
    return fibonacci(n-1) + fibonacci(n-2)

Throughout this chapter, use zero-based indexing: F(0)=0, F(1)=1, and F(n)=F(n−1)+F(n−2). Naive recursion evaluates the same states repeatedly; its running time is Θ(φⁿ), where φ=(1+√5)/2. Memoization evaluates each distinct state once.

13.3Top-down and bottom-up DP

def fib(n, memo):
    if n < 2: return n
    if memo[n] == -1:
        memo[n] = fib(n-1,memo)+fib(n-2,memo)
    return memo[n]

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]

13.40/1 knapsack

Each item is either included once or excluded. KP(i,W_c) is the maximum profit using items 1…i with total weight at most W_c.

There are exactly two choices for item i: exclude it and retain capacity W_c, or include it and leave capacity W_c−w_i. In both cases, only items 1…i−1 remain available. Taking the maximum covers all feasible subsets. The base case assumes positive item weights, so a zero-capacity knapsack earns zero.

13.5Building the knapsack table

Worked example: four items have profits [1,2,5,6] and weights [2,3,4,5], with capacity W=8. State KP(i,w) uses only the first i items and capacity at most w. Each transition reads the previous row, preventing an item from being selected twice.

profit = [0, 1, 2, 5, 6]
weight = [0, 2, 3, 4, 5]
kp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for w in range(1, W + 1):
        if weight[i] <= w:
            kp[i][w] = max(profit[i] + kp[i-1][w-weight[i]], kp[i-1][w])
        else:
            kp[i][w] = kp[i-1][w]
return kp[n][W]

def knapsack(i, capacity):
    if i == 0 or capacity == 0: return 0
    if memo[i][capacity] != -1: return memo[i][capacity]
    result = knapsack(i-1, capacity)
    if weight[i] <= capacity:
        result = max(result, profit[i] + knapsack(i-1, capacity-weight[i]))
    memo[i][capacity] = result
    return result

13.7Matrix-chain dynamic programming

Every parenthesization has a final split k: multiply the result of A_i…A_k by the result of A_k+1…A_j. Their dimensions are p[i−1]×p[k] and p[k]×p[j]. The cost is the best cost of each subchain plus the cost of this final multiplication. Try every legal k and retain the cheapest.

def matrix_chain_order(p):
    n = len(p) - 1
    m = [[0]*(n+1) for _ in range(n+1)]
    s = [[0]*(n+1) for _ in range(n+1)]
    for length in range(2, n+1):
        for i in range(1, n-length+2):
            j = i + length - 1; m[i][j] = float('inf')
            for k in range(i, j):
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]: m[i][j], s[i][j] = q, k
    return m, s

Fill by increasing chain length l. For l=3, the start index i takes values 1 and 2: first solve A₁A₂A₃, then A₂A₃A₄. In each case j=i+l−1. The start index chooses the subchain; k chooses a split within that subchain.

The split table s[i,j] stores the k that achieved the minimum. Reconstruct the order recursively by splitting at s[i,j] until each subchain contains one matrix. There are O(n²) intervals and at most O(n) splits per interval, giving O(n³) time.

13.8All-pairs shortest paths: Floyd–Warshall

Given a weighted directed graph G=(V,E), find the shortest distance between every ordered pair of vertices. The input is an adjacency matrix A and the output is a distance matrix D. Unlike a single-source shortest-path problem, every vertex acts as a source.

The four-vertex example

The lecture graph has seven directed edges: 1 → 2 (4), 1 → 4 (8), 2 → 1 (9), 2 → 3 (2), 3 → 1 (6), 3 → 4 (1), and 4 → 1 (2). Direction matters: opposite edges may have different weights.

Initialize D⁽⁰⁾=A. Every diagonal entry is 0. Use the edge weight for a direct edge and ∞ when no direct edge exists. Rows identify the source i and columns identify the destination j.

State and recurrence

Keep the best path that avoids k internally, or combine a path from i to k with a path from k to j. Without negative cycles, a shortest path can be chosen without repeating vertices. Splitting a path that uses k gives two subpaths whose intermediate vertices come from 1,…,k−1. This gives the DP recurrence.

Updates at each phase

Each phase checks all 16 ordered pairs. The following entries improve; every other entry keeps its previous value.

Final distances and a shortest route

Pseudocode and Python

Initialize D = a copy of the adjacency matrix
for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:
            D[i,j] = min(D[i,j], D[i,k] + D[k,j])
return D

def floyd_warshall(A):
    n = len(A)
    D = [row[:] for row in A]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D

inf = float('inf')
A = [[0, 4, inf, 8],
     [9, 0, 2, inf],
     [6, inf, 0, 1],
     [2, inf, inf, 0]]
D = floyd_warshall(A)
print(D[1][0])  # 5: vertex 2 to vertex 1 (zero-based Python indices)

13.9Rod-cutting problem

Prices for lengths 1…10 are [1,5,8,9,10,17,17,20,24,30]. For a rod of length n, choose the first piece i and combine its price with the best revenue for n−i.

Assume integer lengths, a listed price for every supported piece length, and no cutting cost. The whole rod must be sold. Choosing i=n sells the rod intact; choosing a smaller i leaves a remainder whose optimal revenue is r[n−i]. Piece lengths may be reused, unlike items in 0/1 knapsack. Set r[0]=0.

def cut_rod(p,n):
    if n == 0: return 0
    q = float('-inf')
    for i in range(1,n+1):
        q=max(q,p[i]+cut_rod(p,n-i))
    return q

def bottom_up_cut_rod(p,n):
    r=[0]*(n+1)
    for j in range(1,n+1):
        q=float('-inf')
        for i in range(1,j+1):
            q=max(q,p[i]+r[j-i])
        r[j]=q
    return r[n]

def memoized_cut_rod(p,n):
    r=[float('-inf')]*(n+1)
    def aux(length):
        if r[length] >= 0: return r[length]
        if length == 0: q=0
        else: q=max(p[i]+aux(length-i) for i in range(1,length+1))
        r[length]=q; return q
    return aux(n)

13.10Longest common subsequence (LCS)

Given two sequences X and Y, find the longest sequence that appears in both in the same relative order. Characters may be skipped, but they may not be rearranged. LCS measures agreement between sequences and is a useful foundation for comparing text and explaining insertion/deletion edits.

Worked example: the same four letters in both sequences

X · 7 characters

ABCBDAB

Y · 6 characters

BDCABA

An LCS is BCBA, with length 4. The figure shows where its characters appear in each sequence. The DP table below establishes that no longer common subsequence exists.

Define the state using prefixes

When the last characters match: an optimal common subsequence can end with that character. Append it to an LCS of the two shorter prefixes. This explains the diagonal dependency and the added 1.

When the last characters differ: they cannot both be the final matched character. Every common subsequence omits at least one of those two positions, so compare the solution that drops X’s last character with the solution that drops Y’s last character. Choose the longer result.

Fill the table row by row, from left to right. Each state uses only the cell above, the cell to the left, or the diagonal cell, all of which are already available. The final length is L[m,n], where m=len(X) and n=len(Y).

Recover the sequence, not just its length

1. Start at L[m,n]. If the current characters match, record that character and move diagonally up-left.
2. If they differ, move to whichever of the upper or left cells has the larger value. Either direction is valid when the values tie; here we choose up.
3. Stop when either prefix becomes empty. Reverse the recorded characters because the walk collected them from right to left.

def longest_common_subsequence(x, y):
    m, n = len(x), len(y)
    dp = [[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]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    i, j = m, n
    result = []
    while i > 0 and j > 0:
        if x[i - 1] == y[j - 1]:
            result.append(x[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], ''.join(reversed(result))

LCS practice problems with explanations

13.11Exercises and checks

Use these questions to check both the computed answer and the reasoning behind it.

1. Improve Fibonacci auxiliary space to O(1) using prev2, prev1, and current.
2. Can DP improve a single factorial computation? No: the recursion has no overlapping subproblems.
3. Can DP implement merge sort? Standard merge-sort subproblems are disjoint, not identical, so memoization adds no benefit.
4. For each DP algorithm, identify the state, recurrence, base case, evaluation order, and returned state.
5. Derive matrix-chain complexity from the length, start-index, and split-index loops.
6. Starting from the four-vertex graph, list the entries improved at each Floyd–Warshall phase. Why must the intermediate-vertex loop be outermost?
7. Compare the direct edge from 2 to 1 with the route 2 → 3 → 4 → 1. What happens if a reachable negative cycle lies on a route?