Last Updated: Mar 27, 2024

# Difference Between Divide And Conquer And Dynamic Programming

## Introduction

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.

## 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.

• 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.

• 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

### 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:

Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of CBasics of Java, etc., along with some Contests and Interview Experiences only on Coding Ninjas Studio

Do check out The Interview Guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like AmazonAdobeGoogle, etc. on Coding Ninjas Studio.

Happy Learning.

Topics covered
1.
Introduction
2.
What is Divide And Conquer?
2.1.
Working of Divide and conquer
2.2.
2.3.
3.
What is Dynamic Programming?
3.1.
Working of Dynamic Programming
3.2.
3.3.