Divide and Conquer vs Dynamic Programming
Divide and conquer and dynamic programming both cut a big problem into small parts to solve one at a time. In the first, each part is new. In the second, the same parts come back, so each answer is saved and used again.
Divide and Conquer
Cutting a big problem into small ones like it. Solve each, then join the answers.
Divide and conquer cuts a big problem into smaller copies of itself. Each small piece is solved, often by splitting again, until the pieces are tiny. Then the answers are joined to answer the big problem. Merge sort, quicksort and binary search all work this way. It is usually written with recursion.
Dynamic Programming
Saving the answers to small parts that repeat. Each is solved once.
Dynamic programming breaks a big problem into small ones that repeat. It saves each small answer. When the same small problem comes up again, it reuses the saved answer. You can save answers as you go from the top; that is called memoization. Or you can fill a table from the smallest case up. It turns many jobs that would take years into ones that take a second.
In one line
- Divide and Conquer
- Cutting a big problem into small ones like it. Solve each, then join the answers.
- Dynamic Programming
- Saving the answers to small parts that repeat. Each is solved once.