From Exponential to Shippable

Take a typical case, made up for illustration. A “did you mean…” feature compared each search against product names with a recursive edit-distance function. It was correct, and a 20-character query took more than ten seconds per comparison, because the recursion solved the same pairs of prefixes over and over: for two 20-character strings with no matching characters, the plain recursion makes about 3.9 × 1014 calls. A table that computed each pair once made the same comparison take microseconds.

Dynamic programming is that move, made deliberately: spot subproblems that repeat, solve each once, and store the answer. There is nothing magic about it. Below is a recipe that works on most DP problems (state, recurrence, base case, order), the choice between top-down and bottom-up, and the tricks that cut memory and work further.

If dynamic programming still feels like magic
  • You can solve DP problems with hints but not from scratch
  • You can't decide between top-down memoization and bottom-up tables
  • You've written 2D arrays where 1D would've worked
  • You can't derive the recurrence even when you know the problem is DP