Divide And Conquer Versus Dynamic Programming
The divide-and-conquer technique breaks down a problem into two or more subproblems, solving the easier problems first and then using the solutions to solve the harder problem. This strategy is used in many areas of mathematics and computer science, as well as in many practical problems. The article contains a detailed description of how this technique works.
You can find additional examples of the division-and-conquer problem, as well as dynamic programming problems, complete with explanations, comments, and example code, at the Algorithms & Data Structures repository for JavaScript. The major difference between divide and conquer and dynamic programming is that divide and conquer merges solutions from the subproblems to get a solution to the main problem, whereas dynamic programming uses results from subproblems to get an optimal solution of the main problem. The divide and conquer algorithm splits a problem into sub-problems and combines these solutions to obtain a solution of the original problem. All solutions to subproblems are collected together to find a solution for the problem.
If one of the subproblems calculated earlier is similar to the current one, then the results from this subproblem are used. The result of each sub-problem is not stored for future reference, while, in a dynamic method, the result of each sub-problem is stored for future reference. Use the dynamic approach when you need the results of one subproblem for use several times in the future. Unlike divide-and-conquer, the dynamic programming approach calculates a subproblem iteratively and stores the solution for future use.
From above, we can infer that dynamic programming is based on divide-and-conquer, which can only be applied if a problem has an optimal substructure and overlaps the sub-problems. Once those two conditions are satisfied, then we can say that such a divide-and-conquer problem can be solved using the dynamic programming method.
Divide and conquer splits problem at one particular point only, while dynamic programming will divide point at each possible point. Dynamic programming divides a major problem into smaller subproblems, but dynamic programming does not independently solve subproblems. Divide-and-conquer is a technique used to design algorithms, which involves splitting a problem into smaller subproblems in hopes the subproblems solutions are easier to come by, then compiling the partial solutions to solve the main problem.
There are different applications of divide-and-conquer method, like binary search algorithms, sorting algorithms. Dynamic programming approaches extend divide and conquer approaches by using two techniques (memorization and tabulation), which both serve a purpose to store and reuse solutions to subproblems, which can dramatically increase the productivity.
We found out that dynamic programming is based on the principles of divide and conquer, which can only be applied when a problem has superimposed sub-problems and optimal substructures (such as Levenshtein distance cases). Divide and conquer is an algorithm which recursively breaks a problem down into two or more sub-problems of the same or related types, until it becomes easy enough to be solved directly. In essence, recursion is based on two key concepts of problem solving: division and conquest, and self-similarity. Divide typically takes the recursive approach of splitting a given problem, until there is no further division of subproblems.
The basic idea behind the first stage is to split a given problem into smaller instances, or sub-problems. Sometimes, we do not have to solve many sub-problems, since these are marked solved in themselves once we have completed the separation phase. We keep diving into the two sub-arrays in smaller instances until we hit a case which cannot be split anymore. The algorithm splits the array in two halves, recursively sorts them, and finally combines the two ordered halves.
Let us move on to trying to solve a few problems using DP and DC approaches, so that this illustration is clearer. To illustrate how a Fibonacci number problem could be solved using a dynamic programming approach, let us get an input value. Overlapping sub-problems: The problem can either be broken into sub-problems that are repeated multiple times, or the problem recursive algorithm solves the same sub-problems repeatedly instead of always producing new sub-problems.
Divide and Conquer algorithms are used in a variety of real-world applications. One common application is in the field of computer vision. Algorithms such as the Haar wavelet transform and the Viola-Jones object detection framework use divide and conquer to quickly identify objects in images. Another common application is in the field of bioinformatics. Algorithms such as sequence alignment and protein folding use divide and conquer to efficiently solve complex problems.
Dynamic programming is also used in a variety of real-world applications. One common application is in route planning. Algorithms such as the Dijkstra algorithm and the Bellman-Ford algorithm use dynamic programming to find the shortest path between two points. Another common application is in finance. Algorithms such as portfolio optimization and option pricing use dynamic programming to make optimal decisions based on uncertain future events.
There is no one-size-fits-all answer to the question of which algorithm design paradigm is better. It depends on the specific problem that needs to be solved. That said, divide and conquer algorithms are usually more efficient than dynamic programming algorithms when the problem can be divided into subproblems that are independent of each other. On the other hand, dynamic programming algorithms are typically more efficient when the subproblems overlap and need to be solved in a certain order.
