Remembering Subproblems
Dynamic programming (DP) is a technique for problems that break into overlapping subproblems — the same smaller problem is needed many times. The core idea is simple: solve each subproblem once and store its answer, then reuse the stored answer instead of recomputing it.
The classic motivation is the naive recursive Fibonacci: . Computed by plain recursion, recomputes twice, three times, and the redundant work explodes exponentially. But there are only distinct subproblems ( through ). Storing each as it is computed collapses the cost to .
DP comes in two styles that compute the same thing:
- Memoization (top-down): write the natural recursion, but cache each result the first time it is computed; on later calls, return the cached value.
- Tabulation (bottom-up): fill a table of subproblem answers from the smallest up, so each entry is ready when larger ones need it.
DP applies when a problem has two features: overlapping subproblems (the same subproblem recurs) and optimal substructure (an optimal solution is built from optimal solutions of its subproblems). Classic DP problems include shortest paths, edit distance, the knapsack problem, and longest common subsequence — each turning an exponential brute force into a polynomial-time solution by remembering subresults.
Common pitfall: confusing dynamic programming with plain divide-and-conquer. Divide-and-conquer suits problems whose subproblems are independent (like merge sort's two halves). DP is for problems whose subproblems overlap — where the whole point is to store and reuse answers rather than recompute them.