Dynamic programming: classic families

The idea

Recognize the family and the table is already drawn

Dynamic programming: basics filled a row of cells, one per position. Two families need a little more:

Two sequences: comparing two strings, a cell dp[i][j] holds the answer for the first i letters of one and the first j letters of the other. The table is a grid, and each cell looks at the cells above, to the left and diagonally above-left.
Items under a limit: choosing items whose sizes must add up to at most (or exactly) some limit, a cell holds the answer for one possible total. Each item either joins or doesn't, which is the 0/1 knapsack family.

In both, the cell's meaning carries the whole decision so far, and the recurrence asks one question about the last step: did the last letters match, was the last item taken?

The rule

For two strings, a cell is a pair of prefixes and the last letters decide the move. For items under a limit, a cell is a total, and each item is offered once, so loop over items outside and totals inside.

Spotting it

Two inputs to line up, or a budget to fill

Two strings: common letters, matching, aligning

A grid over pairs of prefixes, the longest common subsequence family

Fewest insertions, deletions or replacements to turn one string into another

Edit distance: the same grid with three moves

Pick some items so a total is exactly or at most a limit, each item once

0/1 knapsack: a row of totals, filled from the top down

Split a list into two groups with equal or closest sums

Knapsack with half the total as the limit

Moves only right or down through a grid

A grid where each cell comes from above and from the left

Basic

Longest common subsequence: match the last letters or drop one

A subsequence keeps some letters of a string in their order, not necessarily side by side: "ad" is a subsequence of "abcd". The longest common subsequence of two strings is the longest one that is a subsequence of both.

Let dp[i][j] be its length for the first i letters of a and the first j letters of b. If a's i-th letter equals b's j-th, both can end the common subsequence: dp[i][j] = dp[i − 1][j − 1] + 1. If not, at least one of them is unused, so drop it: the larger of dp[i − 1][j] and dp[i][j − 1]. Row 0 and column 0 stand for an empty prefix and stay 0.

One cell per pair of prefixes, O(1) work each: O(m × n) time and space for strings of lengths m and n.

Medium

Equal halves: a 0/1 knapsack over sums

Can a list be split into two groups with the same sum? Only if some subset adds up to half the total. Let can[s] say whether some of the items seen so far add up to s. Offer the items one at a time: an item x makes s reachable if s − x already was.

The inner loop runs from the top sum down. Going upward, can[s − x] might already include this same x, set a moment earlier in the same pass, and x would be used twice. Downward, every can[s − x] still describes the items before x. That one detail is the difference between 0/1 knapsack and the unlimited version (each item reusable, as coins were in coin change).

n items times target + 1 sums: O(n × target) time and O(target) space.

Hard

Edit distance: three moves into every cell

The edit distance between two words is the fewest single-letter insertions, deletions and replacements that turn one into the other. Let dp[i][j] be it for the first i letters of the first word and the first j of the second. Row 0 and column 0 are the cost of building from nothing or deleting everything: j and i.

If the last letters match, they cost nothing: dp[i − 1][j − 1]. If not, the last edit was one of three, so take 1 plus the cheapest: replace (diagonal), delete from the first word (above), or insert into it (left).

Same grid, same O(m × n) cost as the longest common subsequence; only the three moves and their costs changed. Many string problems are this grid with a different rule per cell.

The template

The two tables

1// two sequences
2dp ← (m + 1) × (n + 1) grid, row 0 and column 0 set for empty prefixes
3for i from 1 to m
4 for j from 1 to n
5 if a[i − 1] = b[j − 1]
6 dp[i][j] ← from dp[i − 1][j − 1]
7 else
8 dp[i][j] ← best of dp[i − 1][j], dp[i][j − 1] (and dp[i − 1][j − 1])
9
10// items under a limit, each item once
11can ← row of target + 1 cells, can[0] set
12for each item x
13 for s from target down to x
14 can[s] ← can[s] or can[s − x]

When the limit allows reusing an item, run the inner loop upward instead. When the answer is a count of ways, add instead of taking the best.

Traps

Where the classic tables go wrong

Off by one between the grid and the strings

Cell i of the grid stands for the first i letters, so it compares letter i − 1. Mixing the two shifts every answer.

The wrong loop direction in a knapsack

Upward lets an item be used again; downward uses it once. Pick the one the problem means.

Subsequence versus substring

A common substring must be contiguous: a mismatch resets the cell to 0 instead of taking the best neighbor.

A huge limit

The knapsack table has a cell per total. With a total in the millions, look for another approach.

Rebuilding the answer

The table gives the length or cost. To print the actual letters or edits, walk back from the last cell, following the move that produced each value.

Check yourself

3 questions

1. In the longest common subsequence grid, the last letters of the two prefixes match. What is dp[i][j]?

2. In the equal-halves knapsack, why does the inner loop run from the top sum down?

3. What is the edit distance from "cat" to "cut"?

Takeaways

Remember this

Two-string problems use a grid over pairs of prefixes; each cell decides from the last letters, O(m × n).
Picking items under a limit is the 0/1 knapsack: a row of totals, items outside, totals inside from the top down.
Run the knapsack's inner loop upward when items can be reused, and add instead of taking the best when counting ways.

Practice

Now solve some yourself

Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.