Dynamic programming like divide and conquer method , solves problems by combining the solutions to sub-problems.
Divide-and-Conquer algorithms partition the problem into disjoint sub-problems , solve the sub- problem recursively and then combine their solutions to solve original problem.
In contrast dynamic programming applies when the sub-problem overlap that is when sub-problem share sub-problem
1)Optimal Substructure
2)Overlapping Sub-Problems
A given problem has optimal substructure property if optimal solution of the given problem can be obtained by using optimal solutions of its sub-problems.
For example :-The shortest path problem has the following optimal substructure property.If a node x lies in the shortest path from node u to node v then the shortest path from u to x and shortest path from from x to v. The standard all pair shortest path algorithm like Floyd Warshall and Bellman-Ford typical example of dynamic programming.
Like divide and conquer, Dynamic programming combine solutions to sub-problems.Dynamic programming is mainly used when solution of same sub-problems are needed again and again. In dynamic programming, computed solutions to sub-problems are stored in a table so that these don't have recomputed. So dynamic programming is not used when there are no common(overlapping) sub-problems.
Divide-and-Conquer algorithms partition the problem into disjoint sub-problems , solve the sub- problem recursively and then combine their solutions to solve original problem.
In contrast dynamic programming applies when the sub-problem overlap that is when sub-problem share sub-problem
Feature of Dynamic programing
1)Optimal Substructure
2)Overlapping Sub-Problems
Optimal Substructure
A given problem has optimal substructure property if optimal solution of the given problem can be obtained by using optimal solutions of its sub-problems.
For example :-The shortest path problem has the following optimal substructure property.If a node x lies in the shortest path from node u to node v then the shortest path from u to x and shortest path from from x to v. The standard all pair shortest path algorithm like Floyd Warshall and Bellman-Ford typical example of dynamic programming.
Overlapping Subproblem
Like divide and conquer, Dynamic programming combine solutions to sub-problems.Dynamic programming is mainly used when solution of same sub-problems are needed again and again. In dynamic programming, computed solutions to sub-problems are stored in a table so that these don't have recomputed. So dynamic programming is not used when there are no common(overlapping) sub-problems.
No comments:
Post a Comment