Dynamic programming General method :
- Dynamic programming is an algorithm design method that can be used when the solution can be viewed as the result of a sequence of decisions
- IT solves optimization problems by combining solutions to sub problems
- Unlike divide-and-conquer, which solve the sub problems top-down, a dynamic programming(DP) is a bottom-up technique. The bottom-up approach is given below:
- Start with the smallest sub problems.
- Combining theirs solutions obtain the solutions to sub problems of increasing size.
- Until arrive at the solution of the original problem.
- Dynamic programming is based on the principle of optimality
- The principle of optimality states that an optimal sequence of decisions has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequence with regard to the state resulting from the first decision.
- The development of a Dynamic-Programming algorithm can be broken into a sequence of four steps:
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.
Principle of optimality: It states that “In an optimal sequence of decisions or choices, each subsequence must also be optimal”.
Greedy method vs Dynamic programming method
|S.No.||Greedy method||Dynamic programming|
|1||It is used for obtaining optimal solution.||It is also used for obtaining optimal solution.|
|2||In this method, A set of feasible solutions and picks up the optimal solution.||There is no special set of feasible solutions in this method.|
|3||In this method, the optimal selection is without revising previously generated solutions.||It considers all possible sequences in order to obtain the optimum solution.|
|4||In this method, there is no such guarantee of getting optimal solution.||It is guaranteed that this will generate optimal solution using principle of optimality .|
Applications coming under this approach are:
- Matrix chain multiplication
- Optimal binary search tree
- 0/1-Knapsack Problem
- All pairs shortest path problem
- Travelling sales person problem
- Reliability design
Topic : DP | Algorithms
This article is contributed by A.S.Karthik. if you find any mistake in this article please comment below in comment section email me academyEra.email@example.com