The main difference between divide and conquer and dynamic programming is that the divide and conquer combines the solutions of the sub-problems to obtain the solution of the main problem while dynamic programming uses the result of the sub-problems to find the optimum solution of the main problem.
Divide and conquer and dynamic programming are two algorithms or approaches to solving problems. Divide and conquer algorithm divides the problem into subproblems and combines those solutions to find the solution to the original problem. However, dynamic programming does not solve the subproblems independently. It stores the answers of subproblems to use them for similar problems.
Key Areas Covered
1. What is Divide and Conquer
– Definition, Functionality
2. What is Dynamic Programming
– Definition, Functionality
3. What is the Difference Between Divide and Conquer and Dynamic Programming
– Comparison of Key Differences
Divide and Conquer, Dynamic Programming
What is Divide and Conquer
Divide and conquer divides the main problem into small subproblems. The subproblems are divided again and again. At one point, there will be a stage where we cannot divide the subproblems further. Then, we can solve each subproblem independently. Finally, we can combine the solutions of all subproblems to get the solution to the main problem.
There are three main steps in divide and conquer. They are as follows.
Divide (Break) – Involves splitting the main problem into a collection of subproblems
Conquer (Solve) – Involves solving each subproblem separately
Combine (Merge) – Joins the solutions of the subproblems to obtain the solution of the main problem
What is Dynamic Programming
Dynamic programming divides the main problem into smaller subproblems, but it does not solve the subproblems independently. It stores the results of the subproblems to use when solving similar subproblems. Storing the results of subproblems is called memorization. Before solving the current subproblem, it checks the results of the previous subproblems. Finally, it checks the results of all subproblems to find the best solution or the optimal solution. This method is effective as it does not compute the answers again and again. Usually, dynamic programming is used for optimization.
Elements of dynamic programming are as follows.
Simple subproblems – Divide the original problem into small subproblems that have a similar structure
Optimal substructure of the problem – The optimal solution to the main problem is within the optimal solution to its subproblems
Overlapping subproblems – Situations of solving the same subproblems again and again
Difference Between Divide and Conquer and Dynamic Programming
Divide and conquer is an algorithm that recursively breaks down a problem into two or more sub-problems of the same or related type until it becomes simple enough to be solved directly. However, dynamic programming is an algorithm that helps to efficiently solve a class of problems that have overlapping subproblems and optimal substructure property.
The main difference between divide and conquer and dynamic programming is that divide and conquer is recursive while dynamic programming is non-recursive.
In divide and conquer, the subproblems are independent of each other. However, in dynamic programming, the subproblems are interdependent. Hence, this is another major difference between divide and conquer and dynamic programming.
Time consumption is another difference between divide and conquer and dynamic programming. Divide and conquer solves each subproblem independently. Therefore, it is more time-consuming. Dynamic programming, on the other hand, uses the answers of the previous subproblems. Thus, it is less time-consuming.
Efficiency also makes a difference between divide and conquer and dynamic programming. Dynamic programming is more efficient than divide and conquer.
Merge sort, quicksort, and binary search use divide and conquer while matrix chain multiplication and optimal binary search tree use dynamic programming.
The main difference between divide and conquer and dynamic programming is that the divide and conquer combines the solutions of the subproblems to obtain the solution of the main problem while dynamic programming uses the result of the subproblems to find the optimum solution of the main problem.
1. “DAA Divide and Conquer Introduction – Javatpoint.” Www.javatpoint.com, Available here.
2. “Dynamic Programming Introduction – Javatpoint.” Www.javatpoint.com, Available here.
3. Dynamic Programming | Steps to Design & Applications |, Education 4u, 2 Apr. 2018, Available here.
4. “Dynamic Programming”, Programiz. com, Available here.
1. “Merge sort algorithm diagram” By VineetKumar at English Wikipedia – Transferred from en.wikipedia to Commons by Eric Bauman using CommonsHelper (Public Domain) via Commons Wikimedia
2. “Fibonacci dynamic programming” By en:User:Dcoatzee, traced by User:Stannered – en:Image:Fibonacci dynamic programming.png (Public Domain) via Commons Wikimedia
Leave a Reply