Skip to content
BENIBIX Learn

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.

Development🧮 Algorithms & Data Structures

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.

Example
Lucy's merge sort splits 1,000 names into halves, then quarters, down to single names. Joining them back gives one sorted list.
Why it matters
It turns many slow O(n²) problems into fast O(n log n) ones.
Full entry
Development🧮 Algorithms & Data Structures

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.

Example
Jack works out the 50th Fibonacci number. Saving each smaller one makes 49 additions, not billions of calls.
Why it matters
Route maps, spell checkers and DNA tests all use it. Without it, those jobs would never finish.
Full entry

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.