Dynamic Programming — definition.
Definition
Break an overlapping-subproblem problem into a recurrence and cache results.
Complexity
State × transition cost; typical O(n), O(n²), or O(n·m).
When to use it
- The optimal substructure holds.
- Subproblems repeat (naive recursion is exponential).
- The answer can be phrased as min / max / count over a recurrence.
Representative scenarios
- Ski Lift Tolls — minimum-cost path on a grid.
- DNA Commonality — longest common subsequence.
- Typo Repair Cost — edit distance between strings.
Related patterns
Read the full pattern page: Dynamic Programming — template, code, and drills.
Run the free diagnostic.
Ten-minute patterns quiz. No card. Personalized loop starts on the other side.