DYNAMIC PROGRAMMING
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to sub-problems. (“Programming” in this context refers to a tabular method, not to writing computer code.) Divide-and-conquer algorithms partition the problem into disjoint sub-problems, solve the sub-problems recursively, and then combine their solutions to solve the original problem.
In contrast, dynamic programming applies when the sub-problems overlap that is, when sub-problems share sub sub-problems. In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common sub sub-problems.
A dynamic-programming algorithm solves each sub sub-problem just once and then saves its answer in a table, thereby avoiding the work of re computing the answer every time it solves each sub sub-problem. We typically apply dynamic programming to optimization problems.
Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.
When developing a dynamic-programming algorithm, we follow a sequence of four steps:
1. Characterize the structure of an optimal solution.
2. Recursively defines the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
4. Construct an optimal solution from computed information.
Example: Following are some examples of problems can be solved by dynamic approach.
- Computing a binomial coefficient
- Travelling Salesman problem
- Knapsack Problem
- Fibonacci Series
- Constructing an optimal binary search tree
- Floyd’s algorithm for all-pairs shortest paths
- Scheduling problems etc.
