A method for solving complex problems by decomposing them into overlapping subproblems and storing their solutions (via memoization or tabulation) so that each subproblem is solved only once and redundant computation is avoided; applicable when the problem exhibits optimal substructure and overlapping subproblems.

Principle

Use the principle of optimality: an optimal solution to a problem contains optimal solutions to its subproblems; organize computation around a state representation, recurrence relation, and reuse of computed subresults.

Demonstration

Compute the nth Fibonacci number by storing earlier Fibonacci values (memoization or bottom-up table): instead of exponential recursion, compute F(0), F(1), ... , F(n) once and reuse them. In optimization, solve the 0/1 knapsack by filling a table of best values for capacity and prefix of items to avoid re-evaluating the same combinations.

Misapplication

Applying dynamic programming to problems without optimal substructure (for example, where local optimal choices do not compose into global optimum) or to problems with extremely large state spaces without compression, leading to incorrect results or prohibitive memory consumption.

Consequence

When applicable, exponential naive searches can often be reduced to polynomial-time algorithms; time is traded for space (memo tables), and solutions are reproducible and exact within the chosen representation.

Reversal

Greedy or divide-and-conquer approaches that do not reuse subproblem solutions and that make locally optimal choices without ensuring global optimality; these may be faster but can be incorrect on problems requiring global coordination.

Boundary

Applies to discrete problems with well-defined states and recurrences; excludes problems lacking optimal substructure or where state cannot be compactly represented (e.g., certain non-Markovian or extremely high-dimensional continuous problems) and cases where memory-time trade-offs are unacceptable.

Semantic Tension

Tension exists between memoization (top-down caching) and tabulation (bottom-up iteration), and between dynamic programming and pure divide-and-conquer: both decompose tasks but differ in reuse strategy and ordering.

Synthesis

Dynamic programming systematically turns a recurrence or state decomposition into a computation that reuses solved subproblems, trading memory for time under the organizing idea that optimal global solutions follow from optimal local subsolutions; practical use requires designing states, transitions, and storage limits.