There exist different algorithm design techniques which can be used separately or in combination with others to solve various problems. Some of these are: Divide and Conquer Strategy, Greedy Method, Dynamic Programming. Each of these methods are particularly effective in solving certain class of problems.
Dymamic programming (DP) is a technique which can be used when the solution to a problem requires making a sequence of decisions. The problem can be viewed as made up of a number of subproblems with interdependence among these subproblems. DP can be used when it is required to find the optimal solution to such problems. The following are the characteristics of a problem which can be solved using DP:
Examples of problems where DP can be used
Difference From Other Techniques
Dynamic programming differs from the "Divide and Conquer" (D-and-C) method in the fact that the problems solved by D-and-C can have many non-overlapping subproblems - i.e, new subproblems may be generated when the method is applied.
DP differs from Greedy method in the fact that greedy method looks at the best possible choice at a particular point and uses it -- a kind of local optimization. So, it may not generate optimal solution in some cases.
Steps involved in a DP solution to a problem
Application of DP to a permutation problem (Graph Tour problem)
The Graph Tour problem involves traversing all the nodes in a graph exactly once and returning to the starting vertex in such a way that the total cost is minimized. We will apply each of the above steps to the problem:
[To be continued]