Difference between Divide and Conquer Algo and Dynamic Programming

The Solution to Difference between Divide and Conquer Algo and Dynamic Programming is


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 Divide and Conquer approach

Dynamic Programming Approach enter image description here

~ Answered on 2012-11-24 05:55:16


Most Viewed Questions: