The Core Insight#
Recursion is a useful tool, but naive recursion can be catastrophically slow. Consider computing fib(40) with pure recursion: the call tree branches into two sub-calls at every level, recomputing fib(2), fib(3), and so on millions of times. The root problem is not recursion itself. It is redundant work.
Dynamic programming (DP) is the discipline of recognising and eliminating that redundancy. It applies whenever a problem has two structural properties:
- Overlapping subproblems: the same smaller problem appears more than once in the recursion tree.
- Optimal substructure: an optimal solution to the whole problem can be built from optimal solutions to its subproblems.
When both hold, you can compute each subproblem exactly once, store the answer, and reuse it every subsequent time it is needed. An exponential algorithm collapses to polynomial.