What is "dynamic-programming"

Dynamic programming is a method for constructing algorithms for solving computational problems, especially combinatorial optimization. It is applicable to problems in which the optimal solution can be computed from the optimal solution previously calculated and memorized - in order to avoid recalculation - of other subproblems that, superimposed, make up the original problem. What an optimization problem should have for dynamic programming to be applicable are two main characteristics: optimal substructure and subproblem superposition. A problem presents an optimal substructure when an optimal solution to the problem contains in its interior optimal solutions for subproblems. Subproblem superposition happens when a recursive algorithm reexamines the same problem many times.

Bibliographic References

• Dasgupta, Sanjoy. Algorithms. São Paulo: Mcgraw Hill, 2009.
• Cormen, Thomas. Algorithms: Theory and Practice. 3 ed.: Campus, 2009.