 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.