[algorithm] Difference between Divide and Conquer Algo and Dynamic Programming

Divide and Conquer involves three steps at each level of recursion:

  1. Divide the problem into subproblems.
  2. Conquer the subproblems by solving them recursively.
  3. Combine the solution for subproblems into the solution for original problem.
    • It is a top-down approach.
    • It does more work on subproblems and hence has more time consumption.
    • eg. n-th term of Fibonacci series can be computed in O(2^n) time complexity.

Dynamic Programming involves the following four steps:

1. Characterise the structure of optimal solutions.
2. Recursively define the values of optimal solutions.
3. Compute the value of optimal solutions.
4. Construct an Optimal Solution from computed information.

  • It is a Bottom-up approach.
  • Less time consumption than divide and conquer since we make use of the values computed earlier, rather than computing again.
  • eg. n-th term of Fibonacci series can be computed in O(n) time complexity.

For easier understanding, lets see divide and conquer as a brute force solution and its optimisation as dynamic programming.

N.B. divide and conquer algorithms with overlapping subproblems can only be optimised with dp.