Introduction to Algorithms · 4th Edition
Solving a big problem by remembering the answers to small ones. Watch memoization and tabulation fill in — one cell at a time.
01 — Tabulation
Naive recursion recomputes the same values over and over. Tabulation computes each value exactly once, left to right, reusing the previous two answers.
dp[i] = dp[i-1] + dp[i-2]
02 — 2D Table
Every cell asks one question: do these two characters match? If they do, take the diagonal and add 1. If not, take the best of the top and left neighbours.
Recurrence
if a[i] == b[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
03 — The payoff
Computing fib(30) the naive way. Same answer, wildly different cost.
Recomputes the same subtrees again and again.
function calls
Each subproblem solved exactly once, then reused.
additions
≈ 93,000× fewer operations
The best solution to the whole problem is built from the best solutions to its subproblems.
The same subproblem recurs many times — so solve it once and cache the result.
Top-down memo or bottom-up table — both trade a little memory for a lot of time.