Divide and Conquer Vs Dynamic Programming
Divide and Conquer Vs Dynamic Programming
This article talks about Divide and Conquer Vs Dynamic Programming, approaches for problem solving. As we know, divide and conquer is general problem solving strategy, which first decomposes the larger problem into smaller sub problems. These sub problems are solved independently. Solution of smaller problems are combined to form the solutions to bigger problems. So basically, divide and conquer approach operates in top down manner.
However, dynamic programming is optimization problem. It is used to find the best solution from a set of possible solutions. It uses the principle of optimality to find the best solution. Divide and conquer splits the problem at a specific point only, whereas dynamic programming splits the point from every possible point. The sub problems in dynamic programming are dependent.
Due to independent sub problems, divide and conquer solves similar sub problems multiple times. Dynamic programming stores the solutions to all sub problems in table, and when ever same sub problem is encountered again, it does not solve it but picks the solution from the table. So there won’t be any repetition of work in the case of dynamic programming.
In following table, we have compared both the problem solving approaches
| Divide and Conquer | Dynamic Programming |
| Divide and conquer is the top down approach. | Dynamic programming is bottom up approach. |
| Divide and conquer prefers recursion. | Dynamic programming prefers iteration. |
| In divide and conquer, sub problems are independent. | Sub problems of dynamic programming are dependent and overlapping. |
| Solutions of sub problems are not stored. | Solutions of sub problems are stored in the table. |
| Lots of repetition of work. | No repetition at work at all. |
| It splits input at a specific point. | It splits input at each and every possible point. |
| Less efficient due to rework. | More efficient due to the saving of solution. |
| Solution using divide and conquer is simple. | Sometimes, a solution using dynamic programming is complex and tricky. |
| Only one decision sequence is generated. | Many decision sequences may be generated. |
Additional Reading: Read More