Chapter 12. Dynamic Programming
Dynamic programming (DP) is a commonly used technique for solving a wide variety of discrete optimization problems such as scheduling, stringediting, packaging, and inventory management. More recently, it has found applications in bioinformatics in matching sequences of aminoacids and nucleotides (the SmithWaterman algorithm). DP views a problem as a set of interdependent subproblems. It solves subproblems and uses the results to solve larger subproblems until the entire problem is solved. In contrast to divideandconquer, where the solution to a problem depends only on the solution to its subproblems, in DP there may be interrelationships across subproblems. In DP, the solution to a subproblem is expressed as a function of solutions to one or more subproblems at the preceding levels.
