= Solution
<Dynamic programming> describes a problem by reusable subproblem states and a recurrence, computing each required state once through <memoization> or a bottom-up order. Its benefit comes from sharing answers to overlapping subproblems.
The <principle of optimality> says that, after the information needed by a state has been fixed, the remaining part of an optimal solution is optimal for that state. Otherwise replacing it by a better subsolution would improve the whole solution. A correct state must retain every constraint that can affect later choices.
Back to article page
