Hello Ninjas, In the DSA world, there are many algorithms. Each of these algorithms helps us to find out our results optimally. But sometimes, they require optimization to solve the problem more efficiently.

The two optimization techniques commonly used are Dynamic Programming and Divide and Conquer.

In this article, we will learn more about them. We will also see the difference between divide and conquer and dynamic programming.

What is Divide And Conquer?

Divide and conquer is a programming strategy of dividing a complex problem into small, simple subproblems. Then the sub-problems are computed parallelly. The solutions of the subproblems are combined to generate the final result. Dividing helps to break a complex problem into smaller manageable problems. It is implemented using recursion.

Working of Divide and conquer

The steps involved in divide and conquer are:

Divide: Dividing given problem into sub-problems using recursion.

Conquer: Recursively solving the sub-problems. The direct result is generated if the results are small.

Combine: The results of the subproblems that are part of the recursion are combined to solve the problem.

Advantages Of Divide And Conquer

Parallelism: In this approach, we independently solve the subproblems. It helps in the execution of multi-processor and shared-memory systems. Thus, different subproblems can run on different processors.

Memory Usage: It provides efficient use of memory caches. Using the cache memory solves subproblems without using the slower main memory.

Reduces Difficulty: Here, we Divide the problem into smaller problems. This helps reduce the difficulty of the problem. Thus, making it more efficient than the brute force method.

Disadvantages Of Divide And Conquer

It is majorly implemented using recursion, making it slow.

The system can crash if recursion is carried out beyond the CPU stack.

Due to the large recursive base case, the recursion overhead can become very small.

What is Dynamic Programming?

It is the programming technique of dividing a given problem into smaller subproblems. It is used to find the optimal solution for a problem. It is similar to divide and conquer. Here, a sub-problem is solved just once. It is used to solve optimization problems.

The two properties that suggest the use of dynamic programming are:

Overlapping Sub-Problem: Here, we divide a problem into sub-problems. It is used when the solution of a subproblem is required repeatedly. Example calculating Fibonacci numbers.

Optimal Sub Structure: Here, we divide a problem into sub-problems. It is used if the optimal solution is calculated from the results of its sub-problems. Example Shortest path-finding question.

Working of Dynamic Programming

The steps involved in solving dynamic programming problems are:

Define a small problem and find an optimum solution to this problem. In our example, this is the same as finding the best path from the last intersection to the office.

To define a small sub-problem and find its optimal solution.

Enlarge the scope of this small problem and find the optimal solution to this new problem.

Continuing the above step, we get a sufficiently large problem. The problem now beholds the original problem.

Define the stopping conditions carefully.

Use the results of smaller problems to calculate the original problem result.

Advantages Of Dynamic Programming

Solution: It always gives an optimal solution for a problem.

Efficient: It uses overlapping subproblems to solve the problem. Thus, helps to increase efficiency by preventing overhead calculations.

Application: It can be applied to a variety of problems. These problems can be path-finding or optimization.

Disadvantages Of Dynamic Programming

Memory: It stores the solutions to the overlapping subproblems. Thus, requires huge memory to solve problems.

Complexity: It is difficult to implement. As the problem gets large, the number of subproblems increases. Thus, increasing the complexity of the solution.

Difference Between Divide And Conquer And Dynamic Programming

Parameters

Divide and Conquer

Dynamic Programming

Definition

It is a programming strategy of dividing a complex problem into small, simple subproblems.

It is a programming strategy of dividing a complex problem into small, simple overlapping subproblems.

Time

It is time-consuming as it solves a problem more than once. Thus, doing more work.

It solves a sub-problem exactly once. Therefore, less time-consuming.

Approach

It follows a top-down approach. Recursion is typically used.

It can follow a top-down or a bottom-up approach. Iterations are typically used.

Dependency

Sub-problems are independent of each other.

It has overlapping sub-problems.

Space

It does not store the intermediate result. Thus, less space is required.

It stores the results of the intermediate sub-problems. Thus, more space is required.

Simplicity

It is more intuitive and easy to understand.

It is less intuitive and difficult to implement.

Example

It is used in problems like Binary Search, Quick Sort, and Merge Sort.

It is used in problems like Longest common subsequence, Matrix Chain Multiplication, etc.

Frequently Asked Questions

What is the similarity between Dynamic Programming and Divide and Conquer?

Both are used for solving complex problems. Both follow the approach of dividing a problem into smaller sub-problems. Both can be optimized to give optimal solutions. Both can use recursion to solve a problem.

What is memoization in Dynamic Programming?

Memoization is a dynamic programming approach. It is used to solve complex recursive problems. It is used to optimize the recursion. It involves storing the sub-problem results. It helps to avoid repeated computation.

What are the conditions for solving a problem using Divide and Conquer?

The necessary conditions are the given problem must be divisible into smaller sub-problems. The sub-problems must be easy problems. The complexity of combining the result must be comparable to other algorithms.

Conclusion

The article taught us about Dynamic Programming and Divide and Conquer techniques. We discussed the difference between divide and conquer and dynamic programming. We saw how their work time, space, approach, and dependency differ.

To learn more about divide and conquer and dynamic programming, you can check out our other blogs: