Dynamic programming

Summary

Dynamic programming is a method for designing algorithms that solves a problem through a family of overlapping subproblems. The value of each subproblem is given by a recurrence in terms of smaller subproblems, and each value is computed only once and stored. It applies when optimal solutions are built from optimal solutions of subproblems, and it turns many exponential-time recursions into polynomial-time algorithms. In optimization and control the recurrence is called the Bellman equation.