Tuesday, June 20, 2017

What is the Idea of Developing a DP Algorithm?

The Idea of Developing a DP Algorithm :

Step 1: Structure : Characterize the structure of an optimal solution.

-Decompose the problem into smaller problems, and find a relation between the structure of the optimal solution of the original problem and the solutions of the smaller pronlms.

Step 2 : Principle of Optimality : Recursively define the value of an optimal solution.

-Express the solution of the original problem in terms of optimal solutions for smaller problems.

Step 3 : Bottom-up computation: Compute the value of an optimal solution in a bottom-up fashion by using a table structure.

Step 4 : construction of optimal Solution : Construct an optimal solution from computed information.Steps 3 and 4 may often be combined.