Dynamic programming patterns: knapsack, edit distance, LCS
Apply the knapsack family, sequence alignment, and interval DP, and reconstruct the actual solution rather than only its cost.
The knapsack family
from typing import Sequence
def knapsack_01(weights: Sequence[int], values: Sequence[int], cap: int) -> int:
"""Each item at most once: state (item, capacity), inner loop descending."""
best = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w - 1, -1):
best[c] = max(best[c], best[c - w] + v)
return best[cap]
def knapsack_unbounded(weights: Sequence[int], values: Sequence[int], cap: int) -> int:
"""Unlimited copies: ascending inner loop."""
best = [0] * (cap + 1)
for c in range(1, cap + 1):
for w, v in zip(weights, values):
if w <= c:
best[c] = max(best[c], best[c - w] + v)
return best[cap]
def knapsack_bounded(weights: Sequence[int], values: Sequence[int],
counts: Sequence[int], cap: int) -> int:
"""A limited count per item: split each count into powers of two."""
items: list[tuple[int, int]] = []
for w, v, k in zip(weights, values, counts):
power = 1
while k > 0:
take = min(power, k)
items.append((w * take, v * take)) # one synthetic item per group
k -= take
power <<= 1
best = [0] * (cap + 1)
for w, v in items:
for c in range(cap, w - 1, -1):
best[c] = max(best[c], best[c - w] + v)
return best[cap]
def partition_equal_subset(nums: Sequence[int]) -> bool:
total = sum(nums)
if total % 2:
return False
target = total // 2
reachable = [False] * (target + 1)
reachable[0] = True
for x in nums:
for c in range(target, x - 1, -1):
if reachable[c - x]:
reachable[c] = True
return reachable[target]
if __name__ == "__main__":
print(knapsack_01([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 9
print(knapsack_unbounded([1, 3, 4, 5], [1, 4, 5, 7], 7)) # 11
print(knapsack_bounded([2, 3], [3, 4], [1, 3], 8)) # 11
print(partition_equal_subset([1, 5, 11, 5])) # True| Variant | Constraint | Loop direction | Complexity |
|---|---|---|---|
| 0/1 knapsack | Each item once | Capacity descending | O(n * cap) |
| Unbounded | Unlimited copies | Capacity ascending | O(n * cap) |
| Bounded | Count per item, binary split | Descending over grouped items | O(cap * sum(log k)) |
| Subset sum | Reachability, values not weights | Descending | O(n * target) |
| Partition | Two equal halves | Descending to total/2 | O(n * sum) |
| Fractional | Fractions allowed | Greedy sort | O(n log n) |
Binary splitting turns a bounded count into a set of 0/1 items: a count of 13 becomes groups of 1, 2, 4 and 6. Any number up to 13 is then representable as a sum of whole groups, and the complexity drops from a factor of k to a factor of log k.
LCS, edit distance and reconstruction
from typing import Sequence
def lcs_length(a: str, b: str) -> int:
"""Longest common subsequence: 2D DP over prefixes."""
previous = [0] * (len(b) + 1)
for ca in a:
current = [0] * (len(b) + 1)
for j, cb in enumerate(b, 1):
if ca == cb:
current[j] = previous[j - 1] + 1
else:
current[j] = max(previous[j], current[j - 1])
previous = current
return previous[-1]
def lcs_reconstruct(a: str, b: str) -> str:
"""Keep the full table when you need the actual subsequence."""
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
out: list[str] = []
i, j = n, m
while i > 0 and j > 0: # walk back from the bottom right
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 "".join(reversed(out))
def edit_distance_ops(a: str, b: str) -> tuple[int, list[str]]:
"""Edit distance plus the operations that achieve it."""
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
cost = 0 if a[i - 1] == b[j - 1] else 1
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
ops: list[str] = []
i, j = n, m
while i > 0 or j > 0:
if i > 0 and j > 0 and a[i - 1] == b[j - 1]:
i -= 1; j -= 1
elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
ops.append(f"substitute {a[i-1]} -> {b[j-1]}")
i -= 1; j -= 1
elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
ops.append(f"delete {a[i-1]}")
i -= 1
else:
ops.append(f"insert {b[j-1]}")
j -= 1
return dp[n][m], list(reversed(ops))
def longest_common_substring(a: str, b: str) -> int:
"""A SUBSTRING is contiguous: reset on mismatch, answer is the max anywhere."""
previous = [0] * (len(b) + 1)
best = 0
for ca in a:
current = [0] * (len(b) + 1)
for j, cb in enumerate(b, 1):
if ca == cb:
current[j] = previous[j - 1] + 1
best = max(best, current[j]) # not the corner cell
previous = current
return best
if __name__ == "__main__":
print(lcs_length("ABCBDAB", "BDCABA")) # 4
print(lcs_reconstruct("ABCBDAB", "BDCABA")) # BCBA
print(edit_distance_ops("kitten", "sitting"))
print(longest_common_substring("abcde", "abfde")) # 2- A subsequence need not be contiguous, so the recurrence takes the max of the two prefixes on a mismatch. A substring must be contiguous, so the value resets to zero and the answer is the maximum over the whole table.
- Reconstruction needs the full table. If you only need the length, the space-reduced single-row version is enough and is far cheaper.
- Edit distance with only insertions and deletions is symmetric, so
dist(a, b) == dist(b, a). Add substitution with cost 1 and it stays a metric, which is what makes it usable for clustering. - Comparing characters is a constant-time hash or equality test. For long strings, hashing substrings with a rolling hash turns the inner comparison into
O(1)and opens the door to much faster algorithms.
Interval DP
from typing import Sequence
def matrix_chain_order(dims: Sequence[int]) -> tuple[int, str]:
"""dims has n+1 entries for n matrices. Cost is the number of multiplications."""
n = len(dims) - 1
if n <= 0:
return 0, ""
dp = [[0] * n for _ in range(n)]
split = [[0] * n for _ in range(n)]
for length in range(2, n + 1): # interval length, smallest first
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float("inf")
for k in range(i, j): # the split point
cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
def build(i: int, j: int) -> str:
if i == j:
return f"M{i}"
k = split[i][j]
return f"({build(i, k)} x {build(k + 1, j)})"
return int(dp[0][n - 1]), build(0, n - 1)
def burst_balloons(nums: Sequence[int]) -> int:
"""Pad with 1s so the boundary case needs no special handling."""
vals = [1, *nums, 1]
n = len(vals)
dp = [[0] * n for _ in range(n)]
for length in range(2, n): # the gap between i and j
for i in range(n - length):
j = i + length
for k in range(i + 1, j): # k is the LAST balloon burst
dp[i][j] = max(
dp[i][j],
dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j],
)
return dp[0][n - 1]
if __name__ == "__main__":
print(matrix_chain_order([40, 20, 30, 10, 30]))
print(burst_balloons([3, 1, 5, 8])) # 167💡
Interval DP is filled by increasing interval length, never in index order, because a state depends on strictly shorter intervals inside it. Getting the loop order wrong produces a table of silently incorrect values rather than an error.
FAQ
When does a knapsack need a 2D table?
When the state needs more than the remaining capacity: a count of items used, a parity, or which of several resource limits is binding. Otherwise the 1D capacity array is enough and uses far less memory.
How do I reconstruct the chosen items?
Keep the full table and walk backwards from the last cell, deciding at each step which predecessor produced the value. If you only kept one row, the information is gone and you must store the choices separately.
Related
Dynamic programming: memoisation to tabulation String algorithms: matching, hashing and tries
Last refreshed 2026-09-18.