Difference between Divide and Conquer Algo and Dynamic Programming
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
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
