Dynamic programming II
The second DP lesson graduates to two-dimensional and structured states: comparing two sequences (LCS, edit distance), packing under a budget (0/1 knapsack), optimally parenthesizing (matrix-chain), walking a grid, intervals, and even exponential states packed into a bitmask (small TSP). The throughline is the same five-step method — the states just get richer, and we learn to shrink their space.
Learning objectives
- Design 2-D DP states over pairs of sequences (LCS, edit distance).
- Solve 0/1 knapsack and matrix-chain multiplication with correct transitions.
- Handle grid DP (paths, min-cost) and interval DP (evaluation order matters).
- Encode a set of visited nodes as a bitmask to solve small TSP exactly.
- Reduce 2-D DP space to one or two rows when transitions allow it.
- Reconstruct the optimal object (subsequence, parenthesization, item set).
1 · Longest common subsequence — the model 2-D DP advanced
Given two strings, the LCS is the longest sequence appearing in both, in order (not necessarily contiguous). State: dp[i][j] = LCS length of prefixes A[:i] and B[:j]. Transition: if the last characters match, dp[i][j]=dp[i-1][j-1]+1; else max(dp[i-1][j], dp[i][j-1]). Complexity: Θ(m·n) time and space. It underpins diff, git merges, and DNA alignment.
pythondef lcs(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # extend the match
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# reconstruct by walking back from dp[m][n]
i, j, out = m, n, []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
out.append(a[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(out))
length, seq = lcs("AGCAT", "GAC")
print("LCS length:", length, "one LCS:", seq)
print(lcs("ABCBDAB", "BDCAB"))
LCS length: 2 one LCS: AC
(4, 'BCAB')2 · Edit distance (Levenshtein) advanced
The edit distance is the minimum number of single-character insertions, deletions, or substitutions to turn one string into another — the engine behind spell-check and fuzzy search. State: dp[i][j] = distance between A[:i] and B[:j]. Transition: if chars match, carry dp[i-1][j-1]; else 1 + min of the three edits.
pythondef edit_distance(a, b):
m, n = len(a), len(b)
prev = list(range(n + 1)) # dp for i-1 row; base: transform "" -> b[:j]
for i in range(1, m + 1):
cur = [i] + [0] * n # base: transform a[:i] -> ""
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # substitute
prev[j], # delete
cur[j - 1]) # insert
prev = cur
return prev[n]
print(edit_distance("kitten", "sitting")) # 3
print(edit_distance("sunday", "saturday")) # 3
print(edit_distance("", "abc"), edit_distance("abc", "abc"))
3
3
3 0Θ(min(m,n)) space. You lose easy reconstruction; keep the full table if you must recover the alignment.3 · 0/1 knapsack — pack under a budget expert
Given items with weights and values and a capacity W, choose a subset of maximum value fitting the budget — each item taken or not (0/1). State: dp[i][w] = best value using items 0..i within weight w. Transition: skip item i (dp[i-1][w]) or take it if it fits (val[i]+dp[i-1][w-wt[i]]). Complexity: Θ(nW) — pseudo-polynomial (depends on the numeric value of W).
pythondef knapsack(weights, values, W):
dp = [0] * (W + 1)
for wt, val in zip(weights, values):
for w in range(W, wt - 1, -1): # iterate DOWN so each item used once
dp[w] = max(dp[w], val + dp[w - wt])
return dp[W]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
print("capacity 7 ->", knapsack(weights, values, 7)) # 9 (items 3+5? -> 4+5=9)
print("capacity 10 ->", knapsack(weights, values, 10)) # 13
capacity 7 -> 9
capacity 10 -> 13w from high to low guarantees dp[w-wt] still refers to the previous item's row, so the item isn't reused. Iterating upward would allow reuse — which is exactly the unbounded knapsack (coin-change style).4 · Matrix-chain multiplication — interval DP expert
Multiplying a chain of matrices is associative, but the order of parenthesization hugely changes the scalar-multiplication count. State: dp[i][j] = min cost to multiply matrices i..j. Transition: try every split point k and take the cheapest: dp[i][k]+dp[k+1][j]+p[i-1]·p[k]·p[j]. This is the prototypical interval DP: solve short intervals first, so fill by increasing length. Θ(n³).
pythondef matrix_chain(dims):
"""dims = [p0, p1, ..., pn]; matrix i has shape p[i-1] x p[i]."""
n = len(dims) - 1
dp = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1): # interval length; short first
for i in range(1, n - length + 2):
j = i + length - 1
dp[i][j] = float("inf")
for k in range(i, j): # try every split
cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
dp[i][j] = min(dp[i][j], cost)
return dp[1][n]
# matrices: 40x20, 20x30, 30x10, 10x30
print(matrix_chain([40, 20, 30, 10, 30])) # 26000
print(matrix_chain([10, 20, 30])) # 6000 (single way)
26000
60005 · Grid DP — paths and minimum cost advanced
A grid where you may move only right or down is the friendliest 2-D DP: each cell depends on its top and left neighbours. Two staples: count paths to the bottom-right, and minimum path sum. Both are Θ(mn) and reduce to one row of space.
pythondef unique_paths(m, n):
row = [1] * n # first row: one way to each cell
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j - 1] # from top (old row[j]) + from left
return row[n - 1]
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = grid[0][0]
for j in range(1, n):
dp[j] = dp[j - 1] + grid[0][j]
for i in range(1, m):
dp[0] += grid[i][0]
for j in range(1, n):
dp[j] = grid[i][j] + min(dp[j], dp[j - 1])
return dp[n - 1]
print("unique paths 3x7:", unique_paths(3, 7)) # 28
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print("min path sum:", min_path_sum(grid)) # 7 (1->3->1->1->1)
unique paths 3x7: 28
min path sum: 76 · Bitmask DP — exact small TSP expert
When a state is a subset of a small universe (≤ ~20 elements), encode it as an integer bitmask: bit k set means element k is in the set. The Held–Karp TSP DP uses dp[mask][i] = cheapest route visiting exactly the cities in mask, ending at city i. Complexity: Θ(2ⁿ·n²) — exponential, but far below the n! of brute force, and exact for n≲18.
pythonfrom itertools import permutations
def tsp_held_karp(dist):
n = len(dist)
FULL = (1 << n) - 1
# dp[mask][i]: min cost path visiting `mask`, ending at i (start fixed at city 0)
dp = [[float("inf")] * n for _ in range(1 << n)]
dp[1][0] = 0 # start: only city 0 visited, at city 0
for mask in range(1 << n):
for i in range(n):
if dp[mask][i] == float("inf") or not (mask >> i) & 1:
continue
for j in range(n):
if (mask >> j) & 1:
continue # j already visited
nmask = mask | (1 << j)
cost = dp[mask][i] + dist[i][j]
if cost < dp[nmask][j]:
dp[nmask][j] = cost
return min(dp[FULL][i] + dist[i][0] for i in range(n)) # return to start
def brute_tsp(dist):
n = len(dist)
best = float("inf")
for perm in permutations(range(1, n)):
route = [0] + list(perm) + [0]
cost = sum(dist[route[k]][route[k + 1]] for k in range(len(route) - 1))
best = min(best, cost)
return best
dist = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
print("Held-Karp:", tsp_held_karp(dist), " brute:", brute_tsp(dist))
Held-Karp: 80 brute: 80mask | (1<<j) adds j; (mask >> j) & 1 tests j; mask & (mask-1) clears the lowest set bit; bin(mask).count('1') is the set size. Iterating mask from 0 upward visits subsets in an order where any subset comes after all subsets it contains fewer bits than — handy for DP dependency order.Checkpoint expert
✓ Checkpoint — you can move on when you can…
- Write the 2-D recurrence for LCS and for edit distance from scratch.
- Explain why 0/1 knapsack iterates weight downward and unbounded iterates upward.
- Fill an interval DP (matrix-chain) in the correct order (by increasing length).
- Reduce an LCS/edit/knapsack DP from O(mn) space to O(n).
- Encode a visited-set as a bitmask and read the Held–Karp complexity.
Edit distance and LCS look almost identical. What is the key difference in their recurrences, and why?
Show answer
+1) — mismatches never cost anything, they just skip a character. Edit distance minimizes a cost and a mismatch costs 1 (substitute) while insert/delete each cost 1. So LCS takes a max over two moves; edit distance takes a min over three moves including the substitution diagonal.Why is 0/1 knapsack called pseudo-polynomial rather than polynomial?
Show answer
Θ(nW) is polynomial in the numeric value W, but W takes only log W bits to write down. Measured against the input size in bits, W = 2^(log W) is exponential — so the algorithm is polynomial in the value but exponential in the encoding length, i.e. pseudo-polynomial. (0/1 knapsack is NP-hard; this is why no truly polynomial algorithm is known.)🪜 Practice ladder beginner → industry
Six graded exercises, easy to real-world. Try each before opening its solution.
Context: The grid-path DP with blocked cells — a common warm-up that forces you to handle a base case where the start or path is obstructed.
Your task: Count paths from top-left to bottom-right moving only right/down, where cells with a 1 are obstacles you cannot enter.
Requirements:
- A blocked cell contributes 0 paths.
- If the start cell is blocked, the answer is 0.
- Use a single rolling row for O(n) space.
💡 Hint: dp[j] = 0 if the cell is an obstacle, else dp[j] + dp[j-1].
Show solution
pythondef unique_paths_obstacles(grid):
n = len(grid[0])
dp = [0] * n
dp[0] = 1 if grid[0][0] == 0 else 0
for i, row_cells in enumerate(grid):
for j in range(n):
if row_cells[j] == 1:
dp[j] = 0 # obstacle: no paths through here
elif j > 0:
dp[j] += dp[j - 1]
return dp[n - 1]
print(unique_paths_obstacles([[0,0,0],[0,1,0],[0,0,0]])) # 2
print(unique_paths_obstacles([[0,1],[0,0]])) # 1
print(unique_paths_obstacles([[1,0]])) # 0 (start blocked)
2
1
0Context: A neat reduction: the longest palindromic subsequence of S is just the LCS of S and its reverse — reusing the model 2-D DP you already wrote.
Your task: Find the length of the longest subsequence of a string that reads the same forwards and backwards.
Requirements:
- Either do LCS(S, reversed S), or an interval DP on dp[i][j].
- Verify on strings with obvious palindromic structure.
💡 Hint: If you go the interval route: dp[i][j] = dp[i+1][j-1]+2 when ends match, else max of dropping either end.
Show solution
pythondef longest_pal_subseq(s):
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1 # single char is a palindrome of length 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = (dp[i + 1][j - 1] if length > 2 else 0) + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
print(longest_pal_subseq("bbbab")) # 4 -> "bbbb"
print(longest_pal_subseq("cbbd")) # 2 -> "bb"
print(longest_pal_subseq("agbdba")) # 5 -> "abdba"
4
2
5Context: Interviews often want not just the best value but which items — forcing you to keep the full 2-D table and walk it back.
Your task: Return the maximum value AND the chosen item indices for a 0/1 knapsack.
Requirements:
- Build the full dp[i][w] table.
- Reconstruct: if dp[i][w] != dp[i-1][w], item i was taken.
- Verify the chosen items' weight fits and value matches.
💡 Hint: Walk from dp[n][W] backwards; when the value changes vs the row above, that item was included.
Show solution
pythondef knapsack_items(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
wt, val = weights[i - 1], values[i - 1]
for w in range(W + 1):
dp[i][w] = dp[i - 1][w]
if wt <= w:
dp[i][w] = max(dp[i][w], val + dp[i - 1][w - wt])
# reconstruct
chosen, w = [], W
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
chosen.append(i - 1)
w -= weights[i - 1]
chosen.reverse()
return dp[n][W], chosen
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
best, items = knapsack_items(weights, values, 7)
print("value:", best, "items:", items,
"weight:", sum(weights[i] for i in items))
value: 9 items: [1, 2] weight: 7Context: Implementing regex matching with '.' (any char) and '*' (zero-or-more) is a famously hard 2-D DP — the same shape as edit distance but with the '*' branching rule.
Your task: Return whether pattern p fully matches string s, where '.' matches any single char and '*' matches zero or more of the preceding element.
Requirements:
- State: dp[i][j] = does s[:i] match p[:j].
- '*' either drops the pair (zero occurrences) or consumes one s char if it matches.
- Handle patterns like 'a*' matching empty; verify several cases.
💡 Hint: For p[j-1]=='*': dp[i][j] = dp[i][j-2] (zero) OR (match on p[j-2] and dp[i-1][j]).
Show solution
pythondef is_match(s, p):
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for j in range(1, n + 1): # patterns like a* matching empty string
if p[j - 1] == "*":
dp[0][j] = dp[0][j - 2]
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
zero = dp[i][j - 2]
one = dp[i - 1][j] and p[j - 2] in (s[i - 1], ".")
dp[i][j] = zero or one
elif p[j - 1] in (s[i - 1], "."):
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]
for s, p in [("aa","a"), ("aa","a*"), ("ab",".*"), ("mississippi","mis*is*p*.")]:
print(f"{s!r} ~ {p!r}: {is_match(s, p)}")
'aa' ~ 'a': False
'aa' ~ 'a*': True
'ab' ~ '.*': True
'mississippi' ~ 'mis*is*p*.': FalseContext: Burst balloons is the interval DP that breaks intuition: you think about the LAST balloon to burst in a range, not the first. A rite of passage for interval DP.
Your task: Given balloon values, bursting balloon i yields left*i*right coins (neighbors in the current arrangement). Maximize total coins.
Requirements:
- Pad the ends with virtual value-1 balloons.
- State: dp[i][j] = max coins bursting all balloons strictly between i and j.
- Iterate the LAST balloon k to burst in (i, j): coins = nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j].
- Verify on the classic [3,1,5,8] example (answer 167).
💡 Hint: Choosing k as the last to burst means its neighbors are exactly the fixed ends i and j, decoupling the two sub-intervals.
Show solution
pythondef max_coins(nums):
balloons = [1] + nums + [1]
n = len(balloons)
dp = [[0] * n for _ in range(n)]
for length in range(2, n): # gap between i and j
for i in range(n - length):
j = i + length
for k in range(i + 1, j): # k = LAST balloon burst in (i, j)
coins = balloons[i] * balloons[k] * balloons[j]
dp[i][j] = max(dp[i][j], coins + dp[i][k] + dp[k][j])
return dp[0][n - 1]
print(max_coins([3, 1, 5, 8])) # 167
print(max_coins([1, 5])) # 10
167
10Context: A resource-assignment DP that shows up in scheduling and ad-allocation systems: assign each job to one of a few machines to maximize profit, where a machine handles at most one job. With few machines, a bitmask over machine-availability is exact.
Your task: Given J jobs and M machines (M small), and profit[j][m] for running job j on machine m (or -1 if impossible), assign a distinct machine to each of the first M jobs (or fewer) to maximize total profit. Each machine used at most once.
Requirements:
- State: dp[j][mask] = best profit having considered jobs 0..j-1 with machines in `mask` still free... or equivalently process jobs one at a time, mask = machines already used.
- For each job either skip it or assign it to any free machine.
- Return the best profit; verify against brute-force permutation assignment.
💡 Hint: Process jobs left to right; the mask of used machines is the only state you need beyond the job index. 2^M * J states.
Show solution
pythonfrom itertools import permutations
def max_assignment(profit):
J = len(profit)
M = len(profit[0])
from functools import lru_cache
@lru_cache(maxsize=None)
def best(j, used_mask):
if j == J:
return 0
result = best(j + 1, used_mask) # skip job j
for m in range(M):
if not (used_mask >> m) & 1 and profit[j][m] >= 0:
result = max(result,
profit[j][m] + best(j + 1, used_mask | (1 << m)))
return result
return best(0, 0)
def brute(profit):
J, M = len(profit), len(profit[0])
best = 0
# try assigning each subset of jobs to distinct machines
for r in range(min(J, M) + 1):
for jobs in permutations(range(J), r):
for machines in permutations(range(M), r):
if all(profit[j][m] >= 0 for j, m in zip(jobs, machines)):
best = max(best, sum(profit[j][m] for j, m in zip(jobs, machines)))
return best
profit = [[5, 1, -1],
[-1, 8, 3],
[4, 2, 6]]
print("bitmask DP:", max_assignment(profit), " brute:", brute(profit))
bitmask DP: 19 brute: 19