Some problems break into smaller versions of themselves that overlap: the same sub-problem comes up again and again. Plain recursion would solve it over and over, exponentially often. Dynamic programming solves each sub-problem once and stores the answer in a table, filling it in an order where everything a cell needs is already there.
Two classic examples compare two words, A (down the side) and B (across the top):
The fewest single-letter inserts, deletes and substitutions that turn A into B. Spell checkers, DNA alignment and diff tools all use it. Cell (i, j) holds the edit distance from the first i letters of A to the first j letters of B.
The longest sequence of letters that appears in both words in the same order, though not necessarily
side by side. LCS of ABCBD and BDCAB has length 3 (for example BCB). It is the core of tools like
diff.
The bottom-right cell holds the final number, but not the edits or the letters themselves. To get them, walk back from that cell: at each step, move to the neighbour the value came from. A diagonal move is a keep or substitution (or, for LCS, a letter of the subsequence); up is a delete; left is an insert. When several moves fit, these pages prefer diagonal, then up, then left.
| Both problems | |
|---|---|
| Time | O(m · n): one constant-time step per cell. |
| Space | O(m · n) for the full table (needed for traceback); just two rows if you only want the number. |