algorithm - Difference between Divide and Conquer Algo and Dynamic Programming

Question

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms? How are the two terms different? I do not understand the difference between them.

Please take a simple example to explain any difference between the two and on what ground they seem to be similar.

Answer 1

Divide and Conquer

Divide and Conquer works by dividing the problem into sub-problems, conquer each sub-problem recursively and combine these solutions.

Dynamic Programming

Dynamic Programming is a technique for solving problems with overlapping subproblems. Each sub-problem is solved only once and the result of each sub-problem is stored in a table ( generally implemented as an array or a hash table) for future references. These sub-solutions may be used to obtain the original solution and the technique of storing the sub-problem solutions is known as memoization.

You may think of DP = recursion + re-use

A classic example to understand the difference would be to see both these approaches towards obtaining the nth fibonacci number. Check this material from MIT.

---

Divide and Conquer approach

Dynamic Programming Approach