= Solution
<Dynamic programming> specifies a collection of overlapping subproblems, expresses each answer using smaller subproblem answers, and stores answers so each subproblem is solved once. One may fill a table in dependency order or use <memoization> to compute only requested entries. The key design choice is a state that retains every feature needed by later decisions.
The <principle of optimality> says that, after a decision in an optimal solution, the remaining decisions must solve the corresponding residual subproblem optimally. Otherwise, replacing that residual solution by a better one would improve the entire solution. This replacement argument requires the state to describe the residual constraints completely. Its useful form here is
$$
\boxed{\text{optimal value of a state}=\max_{\text{feasible first decisions}}\{\text{immediate value}+\text{optimal residual value}\}.}
$$
The maximization applies to these value-maximization problems; minimization uses the analogous minimum recurrence.
Back to article page
