Chapter14 Dynamic Programming
Introduction to algorithm
- like the divide-and-conquer method, solves problems by combining the solutions to subproblems.
- typically apllies to optimization problems.
- To develop a dynamic-programming algorithm, follow a sequence of four steps:
- Characterise the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion.
- Construct an optimal solution from computed information.
Step 1-3 form the basis of a dynamic-programming solution to a problem. If you need only the value of an optimal solution, and not the solution itself, then you can omit step 4. When you do perform step 4, it often pays to maintain additional information during step 3 so that you can easily construct an optimal solution.