Dynamic Programming
Dynamic Programming is a general algorithm design technique for solving problems defined by or formulated as recurrences with overlapping sub instances.
Inverted by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by CS.
"Programming" here means "Planning"
Main idea :
- Set up a recurrence relating a solution to a larger instance to solution of smaller instances.
- Solve smaller instances once
- Record solutions in a table
- Extract solution to the initial instance from that table
Dynamic Programming is typically applied to optimization problems. In such a problem can be many solutions. Each solution has a value, and we wish to find a solution with the optimal value.
The development of a dynamic programming
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom up fashion.
4. Construct an optimal solution from computed information.
Example of Dynamic programming algorithms
- knapsack
Inverted by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by CS.
"Programming" here means "Planning"
Main idea :
- Set up a recurrence relating a solution to a larger instance to solution of smaller instances.
- Solve smaller instances once
- Record solutions in a table
- Extract solution to the initial instance from that table
Dynamic Programming is typically applied to optimization problems. In such a problem can be many solutions. Each solution has a value, and we wish to find a solution with the optimal value.
The development of a dynamic programming
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom up fashion.
4. Construct an optimal solution from computed information.
Example of Dynamic programming algorithms
- Computing a binomial coefficient
- Longest common subsequence
- Warshall's algorithm for transitive closure
- Floyd's algorithm for all-pairs shortest paths
- Constructing an optimal binary search tree
- Some instance of difficult discrete optimization problem
- knapsack
No comments