Sequence Dynamic Programming: A Table Indexed by Prefixes

Entry (i, j) answers the question for the first i characters of one string and the first j of the other.

Sequence dynamic programming compares two strings, or two lists, by answering the question for every pair of prefixes and storing each answer in a table. A prefix is the start of a sequence: the first i characters of a string, where i may be 0. This card names that state, explains why the table has an extra row and column for the empty prefix, shows the three neighbours every entry reads, and lists the cues that point to the technique.

For strings a of length m and b of length n, entry (i, j) holds the answer for the first i characters of a and the first j of b. The whole problem is entry (m, n). Each entry depends only on what happens to the last character of each prefix, a[i − 1] and b[j − 1], counting from 0: either they are used together, or one of them is dropped. Dropping a character leaves a shorter prefix, whose entry is already in the table.

Think of comparing two shopping lists by working down both from the top and ticking the items they share. At any moment you have read some of the first list and some of the second, and that pair of positions is all the state you need. The picture breaks in one place: a person reading two lists skips around both and comes back, while the table only ever extends a prefix by one character, and that is what lets it fill in a fixed order.

Row 0 and column 0 hold the answers for an empty prefix, which are known without any work: an empty string shares nothing with any string, and turning an empty string into one of length j takes j insertions. Without them, the first character of either string would have no entry to read. The table therefore has m + 1 rows and n + 1 columns, not m by n.

Three problems share this shape, and the table below sets them side by side. The third has a single sequence, so its table has one index rather than two.

Three sequence problems: what an entry holds, which entries it reads, and where the answer is
Problem	Entry holds	Reads from	Answer
Longest common subsequence of a and b	The longest common subsequence of a's first i and b's first j	The diagonal (i − 1, j − 1) when the last characters match; otherwise above (i − 1, j) and left (i, j − 1)	Entry (m, n)
Edit distance from a to b	The fewest edits turning a's first i into b's first j	Diagonal, above and left, one for each kind of edit	Entry (m, n)
Longest increasing subsequence of one sequence	The longest increasing subsequence ending at position i	Every earlier entry whose value is smaller	The largest entry

A subsequence keeps some of the characters in their original order, possibly with gaps: MON is a subsequence of MONEY and of LEMON. A substring is a subsequence with no gaps. The cues that point to sequence dynamic programming are two strings or lists to compare, the word subsequence, or a question about the fewest edits, insertions or deletions. The table is filled row by row, left to right, because every entry reads only entries above it or to its left.

The cost of a two-sequence table, for lengths m and n

Time: O(m × n), one constant-time step per entry; every case
Space for the answer itself: O(m × n), the whole table, to walk back through it; every case
Space for the length or count alone: O(min(m, n)), two rows of the shorter string; every case

← → move through sections and cards