Skip to content

Dynamic Programming

When a problem has optimal substructure and overlapping subproblems, storing solutions to subproblems converts exponential recursive exploration into polynomial iteration over a DAG of dependencies.

Tension Addressed

Time vs. Space (trading memory for avoiding recomputation)

Recognizable As

Recurrence relations with shared subproblems; tables indexed by problem state; topological ordering of subproblem dependencies.

Canonical Sources

Bellman, Dynamic Programming, 1957; CLRS, Introduction to Algorithms, Chapter 15

Transfers To

Bioinformatics (sequence alignment), natural language processing (parsing), control theory, economics, operations research

Sub-concepts: - Memoization (top-down): Recursive formulation with caching; computes only needed subproblems - Tabulation (bottom-up): Iterative formulation filling table in dependency order; predictable memory access

The key skill is recognizing the subproblem structure: what state fully characterizes a subproblem? Too little state yields incorrect recurrences; too much state explodes the table size.