The Dynamic Programming (DP) is the most powerful design technique for solving optimization problems. It was invented by mathematician named Richard Bellman inn 1950s. The DP in closely related to divide and conquer techniques, where the problem is divided into smaller sub-problems and each sub-problem is solved recursively. The DP differs from divide and conquer in a way that instead of solving sub-problems recursively, it solves each of the sub-problems only once and stores the solution to the sub-problems in a table. The solution to the main problem is obtained by the solutions of these subproblems.
The steps of Dynamic Programming technique are:
- Dividing the problem into sub-problems: The main problem is divided into smaller subproblems. The solution of the main problem is expressed in terms of the solution for the smaller
- Storing the sub solutions in a table: The solution for each sub-problem is stored in a table so
that it can be referred many times whenever required.
- Bottom-up computation: The DP technique starts with the smallest problem instance and
develops the solution to sub instances of longer size and finally obtains the solution of the
original problem instance.
The strategy can be used when the process of obtaining a solution of a problem can be viewed as a sequence of decisions. The problems of this type can be solved by taking an optimal sequence of decisions. An optimal sequence of decisions is found by taking one decision at a time and never making an erroneous decision. In Dynamic Programming, an optimal sequence of decisions is arrived at by using the principle of optimality.
The principle of optimality states that whatever be the initial state and decision, the remaining decisions must constitute an optimal decision sequence with regard to the state resulting form the first decision.
A fundamental difference between the greedy strategy and dynamic programming is that in the
greedy strategy only one decision sequence is generated, wherever in the dynamic programming, a number of them may be generated. Dynamic programming technique guarantees the optimal solution for a problem whereas greedy method never gives such guarantee.