Dynamic Programming vs Divide and Conquer
Before knowing about the differences between dynamic programming and divide and conquer, we should know about dynamic programming and divide and conquer separately.
What is Divide and Conquer?
Divide and conquer is a strategy used for solving a problem. A strategy can be defined as an approach for solving a problem. To solve a computational problem, this strategy has been designed. There are various techniques available to solve the problem, but we have to decide whether the technique is suitable for the problem or not.
Suppose the problem is large, then we break the problem into smaller sub-problems and then solve these subproblems individually. Once all the sub-problems are solved, we will combine the solutions of all the sub-problems to find the solution to the big problem. If the sub-problem is also large, then apply the divide and conquer strategy again to solve the sub-problem. The constraint of divide and conquer strategy is that the sub-problem should be the same as the major problem. Suppose the major problem is sort then the sub-problems should also be sort. The divide and conquer strategy is recursive in nature. If the problem is big, then we solve that problem recursively.
General method of divide and conquer:
Since the dynamic programming is recursive so procedures are recursive and algorithms are recursive.
The following are the problems that can be solved using the divide and conquer strategy:
- Merge sort: Divide the array into two halves, recursively sort the left and right halves, then we will merge these two halves. This technique is known as a merge sort.
- Quick sort: First, partition the array into small items and large items, then recursively sort these two sets. This technique is known as a Quick sort.
Examples of Divide and Conquer:
- Searching: Divide and conquer strategy is used in binary search.
- Sorting: Merge sort and Quick sort are the example of the Divide and conquer technique.
- Tree traversals
- Matrix multiplication
What is Dynamic Programming?
Dynamic programming means dividing the optimization problem into simpler sub-problems and storing the solution to each sub-problem so that each sub-problem can be solved once. Once all the sub-problems are solved, we will concatenate the results of each sub-problem to find the solution to the initial problem.
Every dynamic programming has four steps:
- Dynamic performing is performed in such a way that the problem can be broken down into optimal sub-problems.
- It defines the value of the solution recursively by showing it in terms of optimal solutions for smaller sub-problems.
- We will calculate the value of optimal solutions.
- Construct the optimal solution from the computed values.
Let’s understand each step in a tabular format.
| Step 1 | Structure | Characterize the structure of an optimal solution. |
| Step 2 | Principle of Optimality | It defines the value of an optimal solution recursively. |
| Step 3 | Bottom-up computation | It computes the value of the optimal solution in a bottom-up fashion by using a table structure. |
| Step 4 | Construction of optimal solution | It constructs the optimal solution from the computed value. |
The following problems can be solved using Dynamic programming:
- Optimal substructure: An optimal solution to the problem contains the optimal solutions to all subproblems.
- Overlapping subproblem: A recursive solution contains a small number of distinct subproblems repeated many times.
Techniques of Dynamic programming
There are two techniques to solve the problems:
- Bottom-up approach: Suppose I want to be an amazing coder. First, I will do practising then I will take part in contests. I will practice more and try to improve. After working hard, I will be an amazing coder. This is a bottom-up approach.
- Top-down approach: This approach is the opposite of the bottom-up approach. I will start with the final solution. First, I will be an amazing coder. Then, I will practice more and try to improve. I will take part in contests, and then I will do the practice.
Differences between the Divide and Conquer and Dynamic Programming
| Dynamic programming | Divide and Conquer |
|---|---|
| In dynamic programming, many decision sequences are generated, and all the overlapping sub instances are considered. | In this technique, the problem is divided into small subproblems. These subproblems are solved independently. Finally, all the solutions of subproblems are combined together to get the final solution to the given problem. |
| In dynamic programming, duplications in solutions are avoided totally. | In this method, duplications in sub solutions are neglected, i.e., duplicate sub solutions can be obtained. |
| Dynamic programming is more efficient than Divide and conquer technique. | Divide and conquer strategy is less efficient than the dynamic programming because we have to rework the solutions. |
| It is the non-recursive approach. | It is a recursive approach. |
| It uses the bottom-up approach of problem- solving. | It uses the top-down approach of problem- solving. |