= Solution
<Dynamic programming> \b[solves a problem by storing solutions to overlapping subproblems and combining them according to a recurrence]. Each <dynamic programming state> describes all information needed by subsequent choices. Evaluating states in an order where their dependencies are already available avoids recomputing the same subproblem. A typical optimization recurrence chooses the best transition; a decision recurrence instead combines feasible transitions with Boolean disjunction.
Back to article page
