Divide & Conquer -vs- Dynamic Programming

Both of the paradigm divide the main problem into sub-problems and solve sub-problems. But in Dynamic Programming approach sub-problems are not solved independently. In this case, results of the sub-problems are remembered and used for similar sub-problems.

When to choose which one?

Divide and Conquer should be used when small sub-problems are not evaluated many times. In this scenario, we should use Dynamic Programming approach or Memorization.

For example, in Binary Search, we never evaluate the same sub-problems again. So, we should use Divide and Conquer approach here. On the other hand, for calculating nth number of Fibonacci series, we need to remember the previous calculation because its next number always comes by adding the previous two numbers. Like:
0  1   1  2  3  5  8  13  21........
So, in this type of scenario we should use Dynamic Programming approach.


Some standard algorithms that use Divide and Conquer approach are:

1. Binary Search
2. Merge Sort
3. Quick Sort
4. Strassen's Algorithm
5. Closest Pair of Points
6.  Cooley-Turkey fast Fourier Transform Algorithm.

Some standard algorithms that use Dynamic Programming approach are:

1. Fibonacci Number Series
2. Tower of Hanoi
3. Knapsack Problem
4. Shortest Path of Dijkstra
5. All pair Shortest path by Floyed-Warshall
6. Project Scheduling