Recap: Sequence Dynamic Programming

Prefixes as state, an empty row and column, three neighbours, and a walk back for the answer itself.

Sequence dynamic programming answers a question about two sequences by answering it for every pair of prefixes, in a table with one extra row and column for the empty prefix. This recap lists what the topic established and where, then gathers the recurrences and their costs.

What the topic established, and which card it was on
The idea	Where
Entry (i, j) answers the problem for the first i items of one sequence and the first j of the other	Sequence Dynamic Programming: A Table Indexed by Prefixes
A match extends the diagonal; otherwise keep the larger of above and left; walk back to recover the subsequence	Fill a Longest Common Subsequence Table
The table is m + 1 by n + 1; without the empty prefix Java and TypeScript fail and Python can return a wrong answer	Sizing the Table Without the Empty Prefix
Fill with two loops from 1, walk back while both indices are above 0	Longest Common Subsequence in Python, Java and TypeScript
Edit distance takes 1 plus the cheapest of delete, insert and substitute, with row 0 and column 0 counting up from 0	Compute the Edit Distance Between Two Words
lis[i] extends the best earlier entry with a smaller value; the answer is the largest entry	Longest Increasing Subsequence in O(n²)
tails keeps the smallest ending for each length, placed by a lower bound; its length is the answer	The Idea Behind the O(n log n) Method for Increasing Subsequences
Lines compare like letters, and a diff marks (m − L) + (n − L) lines	Practice: Comparing Two Versions of a Recipe

The three problems differ in what an entry holds and which neighbours it reads, and share the order they are filled in: row by row, so every entry it reads is already there. Their costs are below.

Sequence dynamic programmes and their costs

Longest common subsequence, lengths m and n: O(m × n) time; O(m × n) space to recover it, O(min(m, n)) for the length; every case
Edit distance, lengths m and n: O(m × n) time and the same space choices; every case
Longest increasing subsequence by lis[i]: O(n²) time, O(n) space; every case
Longest increasing subsequence by tails: O(n log n) time, O(n) space; every case

Knowing several strategies raises the question of which to try first. Choosing a Design Strategy, the next topic, reads a problem's cues to pick between divide and conquer, backtracking, greedy and dynamic programming.

← → move through sections and cards