Dynamic Programming

A problem has optimal substructure when an optimal solution can be constructed from optimal solutions of its subproblems. This is the property that lets DP combine subproblem answers without revisiting their internal choices.

DP applies when the recursion revisits the same subproblems many times (overlapping subproblems). Caching each subproblem's answer turns exponential recomputation into polynomial work. Contrast with divide-and-conquer, whose subproblems are typically disjoint.

Memoization is top-down: recurse and cache results lazily, computing only reachable states. Tabulation is bottom-up: fill a table in dependency order iteratively. Both share the recurrence; tabulation avoids recursion overhead and eases space optimization, memoization avoids computing unneeded states.

The DP state is the set of parameters that fully captures a subproblem so its answer is independent of how that state was reached. A good state is minimal yet sufficient; the number of distinct states bounds the table size and is the main driver of complexity.

The transition is the recurrence expressing a state's value from already-known states. Base cases are the smallest states with directly known values that anchor the recurrence. Total time is roughly (number of states) × (cost per transition).

In tabulation, states must be filled in an order respecting dependencies: each state is computed only after all states it depends on. This is a topological order of the DP dependency DAG; for interval DP it is increasing length, for tree DP it is post-order.