Card 04/ 07
Divide and Conquer vs Dynamic Programming vs Greedy vs Backtracking
Four strategies, told apart by their subproblems, their choices and their cost.
Divide and conquer, dynamic programming, greedy algorithms and backtracking differ in three things: how their subproblems relate, how many choices they try at each step, and what that costs. This card sets the four side by side on those three axes, then separates the two pairs most often confused.
All four reduce a problem to smaller instances of itself and build the answer from theirs. They part company on whether those instances overlap, and on whether the algorithm commits to one choice or tries several.
| Strategy | Subproblems | Choices at each step | Typical cost | Example in this subject |
|---|---|---|---|---|
| Divide and conquer | Independent parts, each solved once | None: every part is solved and the answers combined | Set by the recurrence, often O(n log n) | Merge sort |
| Dynamic programming | Overlapping, each solved once and stored | Every choice, keeping the best or the total | Number of states × choices per state | Fewest coins; longest common subsequence |
| Greedy | One left after each choice | One, proved safe and never revisited | Usually the sort, O(n log n) | Meetings by earliest finish |
| Backtracking | A tree of partial candidates | Every choice, undone after it is explored | Exponential in the worst case, cut by pruning | Permutations; n queens |
Divide and conquer and dynamic programming are both recursive, and the difference is whether a subproblem comes back. Merge sort's halves are separate ranges of the array, so no call is ever repeated, and storing their answers wastes memory, as Memoising Subproblems That Never Repeat counts. Fibonacci numbers and fewest coins ask for the same smaller value many times, so storing it is where the saving comes from.
Greedy and dynamic programming can work on the same subproblems, and the difference is how many choices each tries. With coins of 1, 5, 6 and 9, both see amount 11 as a last coin plus a smaller amount. Greedy takes the largest coin and pays 3 coins; the table tries all four and pays 2. Greedy is right only where an exchange argument proves its one choice safe.
The rule follows from the axes. If every candidate must be listed, backtrack. If one choice can be proved safe, be greedy. If the subproblems repeat, use a table. If the parts are independent, divide and conquer.
← → move through sections and cards