sequence alignment
Real-world matching is rarely exact. A spell-checker must see that "recieve" is one swap away from "receive"; a DNA tool must align two genes that differ by a few mutations; diff must spot that two file versions are mostly the same with a few inserted or deleted lines. Sequence alignment is the general problem of measuring and finding the best correspondence between two strings when small differences — insertions, deletions, substitutions — are allowed.
The standard formulation lines the two strings up, possibly inserting gaps, and scores the alignment by summing per-column costs: a match (often free), a substitution (a mismatch penalty), or a gap (an insertion or deletion penalty). The best alignment is the one of minimum total cost (or maximum total score). This is solved by dynamic programming. Build a table D where D[i][j] is the best cost to align the first i characters of one string with the first j of the other. The recurrence is D[i][j] = min of three choices: D[i-1][j-1] plus the cost of matching/substituting the current pair, D[i-1][j] plus a gap (delete from the first string), and D[i][j-1] plus a gap (insert into the first string). Filling the table in order takes O(n*m) time and O(n*m) space, and tracing back through the choices reconstructs the actual alignment. When match cost is 0, mismatch and gap are 1, this is exactly edit (Levenshtein) distance; with scoring matrices it becomes the Needleman-Wunsch (global) or Smith-Waterman (local) alignment of bioinformatics.
Sequence alignment is the bridge from exact pattern matching to the messy approximate matching the real world demands, and it is one of the most important applications of dynamic programming. The cost is the honest limitation: the straightforward DP is O(n*m), which is fine for words but expensive for two whole genomes; the field has rich speedups (banding when you only allow few differences, Hirschberg's method to cut space to O(n), and heuristic tools like BLAST that trade guaranteed optimality for speed). It connects directly to the longest common subsequence and edit distance, which are special cases of the same table — see those entries for the underlying DP machinery.
Align "kitten" and "sitting" with cost 1 per substitution/gap. Best alignment: substitute k->s, substitute e->i, and insert g at the end — three operations, so the edit distance is 3. The DP table's bottom-right cell holds this 3, and tracing back the chosen min-arrows recovers exactly these three edits.
A two-dimensional DP scores match/substitute/gap per cell; the corner cell is the alignment cost.
The basic DP is O(n*m) in both time and space, which is too much for genome-scale inputs — use banding, Hirschberg's linear-space trick, or heuristics like BLAST when optimality can be relaxed. Edit distance and longest common subsequence are special cases of this same table, not separate algorithms.