Divide & Conquer vs Dynamic Programming

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.

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.

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

You can also take the example of Merge sort here to know whether Dynamic Programming can be used there or not?

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.