Classic sequence and grid problems
Many famous DP problems involve sequences and grids. Their tables reveal structure in strings, from spell-checkers to DNA comparison.
Longest increasing subsequence
Given a sequence, find the longest subsequence whose values strictly increase, not necessarily adjacent. DP state: L[i] = length of the longest increasing subsequence ending at position i. Recurrence: L[i] = 1 + max L[j] over j < i with a[j] < a[i], or 1 if none. This is O(n^2); a clever method with binary search achieves O(n log n).
Longest common subsequence
The longest common subsequence (LCS) of two strings is the longest sequence appearing in both in order. State: C[i][j] = LCS length of the first i characters of X and first j of Y. If X[i] equals Y[j], C[i][j] = C[i - 1][j - 1] + 1; otherwise it is the larger of C[i - 1][j] and C[i][j - 1]. This takes O(mn) time and underlies diff tools that compare file versions.
Edit distance
Edit distance, or Levenshtein distance after Vladimir Levenshtein's 1965 work, counts the fewest insertions, deletions, and substitutions to turn one string into another. State: D[i][j] for prefixes. D[i][j] = D[i - 1][j - 1] if characters match, otherwise 1 + the minimum of D[i - 1][j] (delete), D[i][j - 1] (insert), and D[i - 1][j - 1] (substitute). Spell-checkers, DNA alignment, and fuzzy search use it.
Grid paths
Counting paths from the top-left to the bottom-right of a grid moving only right or down: paths[r][c] = paths[r - 1][c] + paths[r][c - 1], with the first row and column all 1. With blocked cells set to 0, the same table handles obstacles. Replacing sums with minimums over cell costs gives the cheapest path through a grid.
Space optimisation
Many 2D tables depend only on the previous row, so you can keep two rows, or even one, cutting memory from O(mn) to O(min(m, n)). Hirschberg's algorithm uses this to recover an actual LCS or alignment in linear space. Reconstruction usually needs either the full table or such clever techniques.
Maximum subarray
Find the contiguous subarray with the largest sum. Kadane's algorithm keeps best_ending_here = max(x, best_ending_here + x) and the best seen overall, in one O(n) pass. It is DP with a state of one number: the best sum of a subarray ending at the current position.
Interval DP
Some problems combine intervals. Matrix-chain multiplication chooses the order of multiplying a chain of matrices to minimise scalar multiplications: cost[i][j] = min over split k of cost[i][k] + cost[k + 1][j] + the cost of multiplying the two results. Tables are filled by increasing interval length, in O(n^3). Optimal binary search trees and parsing algorithms use similar structures.
Worked example
Edit distance from "cat" to "cut": the table's first row and column are 0 to 3. Matching c with c costs nothing; a versus u needs a substitution; t matches t. The final cell D[3][3] = 1: substitute a with u. From "kitten" to "sitting" the distance is 3: substitute k with s, substitute e with i, and insert g.
Key takeaways
Longest increasing subsequence uses L[i] over earlier smaller values in O(n^2), or O(n log n) with binary search. LCS fills an m x n table in O(mn) and powers diff tools. Edit (Levenshtein) distance minimises insertions, deletions, and substitutions for spell-checking and DNA alignment. Grid DP counts or optimises paths. Keeping only recent rows saves memory. Kadane's algorithm finds the maximum subarray in O(n). Interval DP, as in matrix-chain multiplication, fills tables by increasing length.
Flashcard
Longest increasing subsequence
Check your understanding
How many monotone (right and down only) paths cross a 3 x 3 grid of cells from top-left to bottom-right cell?