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](https://i.stack.imgur.com/QBJIj.png)
Dynamic Programming Approach
![enter image description here](https://i.stack.imgur.com/rFqdb.png)
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…