Memoisation and dynamic programming

Memoisation: cache the recursion

The textbook example is Fibonacci, where fib(n) = fib(n − 1) + fib(n − 2). Written directly, fib(30) recomputes fib(28) twice, fib(27) three times and so on, so the number of calls grows exponentially. A cache keyed by n fixes it without changing the shape of the code:

From 2.7 million calls to 31: one per distinct subproblem. Python has this built in as the @functools.cache decorator (and @lru_cache(maxsize=…) for a bounded version). Memoisation is only correct for pure functions, ones whose result depends only on their arguments. It is also the same idea as an application cache in front of a database, with the same hard question: when does a stored answer stop being true?

Tabulation: fill a table

Memoised recursion still uses the call stack, and its depth can be a problem. Tabulation computes subproblems in an order where each one's inputs are already known, usually with plain loops. Edit distance, the minimum number of single-character inserts, deletes and substitutions to turn one string into another, is a good real example: it powers spell-check suggestions, fuzzy search and parts of diff tools.

Let d[i][j] be the distance between the first i characters of a and the first j of b. Turning nothing into j characters takes j inserts, so the first row is 0, 1, 2, …. Every other cell is the cheapest of three moves: delete from a (d[i−1][j] + 1), insert into a (d[i][j−1] + 1), or substitute (d[i−1][j−1], plus 1 if the characters differ). Each row only needs the row above it, so two rows are enough:

"kitten" to "sitting" is 3: substitute k→s, substitute e→i, insert g. The table has O(m × n) cells, so the time is O(m × n); keeping two rows makes the memory O(n).

Recognising a DP problem

Look for two properties. Optimal substructure: the best answer for the whole is built from the best answers for parts (the shortest route to C through B contains the shortest route to B). Overlapping subproblems: the same parts come up again and again. Typical shapes are prefixes of one or two sequences (edit distance, longest common subsequence, the problem behind diff), capacities (knapsack, making change with the fewest coins), and positions in a grid. Write the recurrence first, check how many distinct states it has, and that number times the work per state is your running time.