DIVIDE AND CONQUER VS DYNAMIC PROGRAMMING

 

In this blog, we will see the similarities and differences between Dynamic Programming and Divide-and-Conquer approaches.

Divide-and-Conquer

Divide-and-conquer is a technique used for designing algorithms that consist of dividing the problem into smaller subproblems hoping that the solutions of the subproblems are easier to find and then composing the partial solutions into the solution of the original problem. Divide and Conquer algorithm consists of a dispute using the following three steps

1. Divide the original problem into a set of subproblems.
2. Conquer: Solve every subproblem individually, recursively.
3. Combine: Put together the solutions of the subproblems to get the solution to the whole problem.

Dynamic Programming

Dynamic Programming is a technique for solving problems with overlapping subproblems. In this, we store the result of the sub-problem that is solved once for future re-use. The technique of storing sub-problem solutions is called memoization.

There are two key attributes that problems have in order for it to be solved using Dynamic Programming.

• Optimal substructure - The optimal solution can be constructed from optimal solutions to its subproblems.
• Overlapping sub-problems - The problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.

If these two attributes are there, then we can use two techniques (memoization and tabulation) that both have the purpose of storing and re-using sub-problems solutions that may drastically improve performance.

WHEN TO USE DYNAMIC PROGRAMMING -

Dynamic programming is used where we have problems, which can be divided into similar sub-problems, so that their results can be re-used. Mostly, these algorithms are used for optimization. Before solving the in-hand sub-problem, dynamic algorithm will try to examine the results of the previously solved sub-problems

WHEN TO USE DIVIDE AND CONQUER-

Divide and Conquer should be used when same subproblems are not evaluated many times. Otherwise Dynamic Programming or Memoization should be used. For example, Binary Search is a Divide and Conquer algorithm, we never evaluate the same subproblems again

Dynamic Programming: Extension of Divide and Conquer

The dynamic programming approach is an extension of the divide-and-conquer problem. It extends Divide-and-Conquer problems with two techniques ( memorization and tabulation ) that stores the solutions of sub-problems and re-use whenever necessary.

Let us understand this with a Fibonacci Number problem.

Example

Problem Description: Find nth Fibonacci Number. Any term in Fibonacci is the sum of the preceding two numbers. We will discuss two approaches

• Divide and Conquer
• Dynamic Programming

Solution 1 - Divide and Conquer

In this, we divide it down to two subproblems to calculate (n-1)th and (n-2)th Fibonacci numbers and now we add(combine) these results to get our nth Fibonacci number.

Pseudo Code

int fib(int n)
{
    if(n <= 2)
        return 1
    return fib(n-1) + fib(n-2)
}

Analysis

The recurrence relation for the above solution is

T(n) = T(n-1) + T(n-2) + o(1)

Time Complexity: O( 2^(n/2))

Solution 2 - Dynamic Programming

We will use the same relation, but we will now store the results of the problem that we solved.

For Example, fib(3) will be calculated for both fib(4) and fib(5). So, we can memorize these result in an array.The idea is to store the fib(n) as it is calculated in a table

Pseudo Code

m = {} 
int fib(int n)
{
    if( n in m )
    {
        return m[n]
    }
    if(n <= 2)
    {
        m[n] = 1
        return m[n]
    }
    m[n] = fib(n-1) + fib(n-2)
    return m[n]
}

Analysis

For every i, belongs to [1,n], we will calculate fib(i) once. So, recurrence relation for the above is

              T(n) = T(n-1) + o(1)

Time Complexity: O(n)

From the above, you can conclude that divide-and-conquer has overlapping sub-problems and storing the sub-problems are possible and in this way, Dynamic Programming comes into the picture.

Difference between Dynamic Programming and Divide-and-conquer

Let us take an example of Binary Search.

Binary Search Problem that is also known as a half-interval search, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target can't lie is eliminated and the search continues on the remaining half until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

The above idea leads to the Divide-and-Conquer principle. But can we apply Dynamic Programming to it? (Think?).

No, we can't use DP to it because there are no overlapping sub-problems. Every time we split the array into completely independent parts. So, the solutions of the sub-problems cannot be re-used somewhere else. 

We summarizes all the previous discussions and enumerate the main differences in a table -

---

Conclusion

From the above, we can conclude that dynamic programming is based on divide-and-conquer and it can be applied only when the problem has optimal substructure and overlapping sub-problems. Despite the resemblance of these two strategies, they remain different, with particular uses.While both approaches help reduces the solution’s complexity, sometimes they can do the opposite as well. So it remains the mission of the researcher to wisely choose the right strategy to apply to solve a problem