Difference Between Divide and Conquer and Dynamic Programming in Tabular Form
Divide and Conquer and Dynamic Programming Difference
The Key Difference Between Divide and Conquer and Dynamic Programming is that in Divide and Conquer method first divides the problem into sub-problems. Then solve sub-problems recursively to obtain a separate result for each sub-problem. Then combine the results of sub-problems to get a final result of the main problem. Whereas Dynamic Programming divides a problem into sub-problems, each sub-problem is solved only once. There is no recursion in dynamic programming.
Divide and Conquer vs Dynamic Programming Comparison Chart
|Divide and Conquer
|The problem is divided into small subproblems. These subproblems are solved Independently. Finally, all the solutions of subproblems are collected together to get the solution to the given problem.
|In dynamic programming, many decision sequences are generated and all the overlapping substances are considered.
|Divide and conquer are less efficient.
|Dynamic programming is efficient than the divide and conquers strategy.
|Consume More time for execution.
|Consume less time for execution.
|Divide and Conquer is Recursive.
|Dynamic Programming is non Recursive.
|Divide and Conquer is a Top-down approach.
|Dynamic Programming is a Bottom-up approach.
|Divide and Conquer Subproblems are independent of each other.
|In Dynamic Programming Subproblems are interdependent.
|Example: Binary Search and Merge Sort
|Example: Matrix Multiplication, Fibonacci Number