Dynamic programming is an algorithmic technique closely related to divide and conquer. Yet, divide and conquer is essentially recursive and therefore “top-down” while dynamic programming is “bottom-up”. To learn more about dynamic programming and divide and conquer algorithms, you can browse AlgoMonster.
Divide and conquer
D&C is one of the most important and widely used techniques in computer science.
Wikipedia says divide and conquer is an algorithm design method. And similar to dynamic programming, divide-and-conquer solves an optimization problem by breaking down it into smaller ones. Each of these sub ones is of the same nature as the original problem. To solve the problem you need, combine the solutions of the subproblems.
Steps how D&C algorithm works
The divide and conquer algorithm works generally in the following steps.
- Divide (Split). Splitting up the problem into smaller pieces is the first step.
- Conquer (Tackle). This method then solves subproblems in a recursive fashion to produce a unique result for each of them.
- Combine (Merge). To solve the problem, the combine is the final step in divide and conquer. This combines all subproblems into one overall solution to the original problem.
To sum up, in a funny way, it’s similar to eating a large cake. You cut it into small pieces. Then, you eat each piece one at a time.
The advantages of the divide and conquer algorithm
The Divide and conquer algorithm is a powerful technique. And this strategy has many benefits.
Efficient memory accessibility
If a subproblem can be solved in the cache, it is divided small enough. In principle, you can tackle all subproblems using the same cache. The divide and conquer algorithm is therefore well-suited to efficient memory caches.
Dealing With Tough Problems
Before one can solve conceptually complex problems, all one needs to do is to figure out how to divide them into easier ones. Divide them until it’s easy enough to be solved directly. Then, you solve the complex problems by combining the solutions you got.
Offering algorithm efficiently
Many algorithms are built on the divide-and-conquer algorithm. Actually, it is used to discover efficient algorithms. Such algorithms include fast Fourier transforms and quicksort and mergesort algorithms.
Dynamic programming
Dynamic programming solves optimization problems by cutting them into smaller pieces. And, this algorithm calculates each of the smaller pieces of subproblems only once. Then, it saves or caches the results. To solve the given problem you will need to first break it down into smaller subproblems that are related. As a result, since you have stored the previously calculated outcomes, there’s no troublesome recalculation.
Steps of solving a problem with dynamic programming
- Tackle the decomposed subproblems to find their optimal solutions.
- Compute each sub-problem. The sub-problems are related. And these interdependent sub-problems form a recursion relation. That is to say, the same sub-problems are showing up again. Yet, with memoization, you don’t have to recalculate each of them. Just use the results it remembers.
- Achieve the final goal. By putting the smaller optimal solutions to all the sub-problems, you successfully get an optimal solution to your target problem.
Dynamic programming and divide and conquer
The main difference between the divide and conquer algorithm and DP is that the subproblems can be solved independently. Divide and conquer don’t allow for recursion, but DP does. Subproblems can only be solved once in divide & conquer because of that.
Dynamic programming subproblems are overlapping, unlike divide and conquer. To solve a larger subproblem of DP, you will need to know the results of each subproblem. This means that a solution to a subproblem must be found to solve a larger subproblem.
You can use memoization in dynamic programming to save previously-solved outcomes. So, immediate use of these outcomes is available when the same problem shows up again.
Overall comparison of dynamic programming and D&C
Divide and conquer: Split the problem into smaller sub ones, conquer them all recursively, and then construct the solutions to find the final solution to your given problem.
Dynamic programming: Decompose an issue into smaller pieces, then, deal with each one once, and save the results in a table. The original solution can then be retrieved from these saved results.
Divide and conquer is just like DP with recursion. And they both simplify the big problem. However, how they get the ultimate solution is not the same.
Conclusion and suggestion
With what we have discussed above, let’s recap the differences between these two similar algorithms.
| Divide and conquer (D&C) | Dynamic programming(DP) | ||
| What is it about? | It is an algorithmic method that recursively splits a problem into subproblems. You can solve these simpler sub problems. | DP is also an algorithmic approach of solving problems. Yet, the problem contains overlapping sub problems and optimal substructures. It break the problem down into smaller pieces. | |
| Features of the subproblems | No subproblems are dependent. Sub problems are just smaller version of the original problem. They share the same nature as the original problem. | All related subproblems are interconnected/interdependent. | |
| Is it recursive? | Yes, it is. | No, it’s not recursive. | |
| Efficient or not? | Less efficient. | Enhanced efficiency. | |
| Time it costs to solve problems? | D&C needs longer time. Because in D&C, it deals with each sub pieces independently. It means that it needs to solve each of the problems once. | Generally, DP is more time-efficient. It takes shorter time to solve the problems. Because of the use of memoization, it reuses the previous answers of the subproblems without calculating it again and again. Each kind of the same sub problems will be solved once only. | |
| Applications of this algorithm | Quicksort and mergesort algorithms, binary search and fast Fourier transforms. | Matrix chain multiplication, optimal binary search tree. |
Final thoughts
Well, these two programming algorithms are not that hard to distinguish, right? And we hope that this article helps.
For beginners of dynamic programming, you can start by reading books about DP and other programming languages. In fact, it’s better to know the general idea before you dive deeper into it. Or you can check out the programming course or articles online.
There is a lot of information about dynamic programming or coding courses. Here, we recommend you algo.monster. Google to see what you can find on there.
