Recap: Choosing a Design Strategy

Independent, overlapping, safely greedy or exhaustive: the subproblems decide.

Choosing a design strategy comes down to four questions about the subproblems, asked in a fixed order. This recap lists what the topic established and where, then gives the four questions with the strategy each one leads to.

What the topic established, and which card it was on
The idea	Where
List every candidate, prove one choice safe, find repeats, find independent parts: checked in that order	Choosing a Design Strategy by the Shape of the Subproblems
A failing greedy rule becomes a table that tries every choice the rule chose among	Replacing a Failing Greedy Rule With a Table Over Amounts
A search whose state (index, left) repeats becomes dynamic programming with a memo keyed by it	Memoising a Backtracking Search Whose States Repeat
The four differ in subproblems, choices and cost; overlap and proof separate the confused pairs	Divide and Conquer vs Dynamic Programming vs Greedy vs Backtracking
A memo on independent subproblems stores every call and is never used	Memoising Subproblems That Never Repeat
Four problems, four strategies, each chosen by the order of the questions	Practice: Naming the Strategy for Four Problems

Each question below names a property of the problem, and the first that holds picks the strategy. When none is clear yet, write the backtracking search and memoise it if its states repeat.

The four questions and the strategy each leads to

Must every candidate be listed?: Backtracking
Can one choice be proved safe?: Greedy
Do subproblems recur, with a best value or a count asked for?: Dynamic programming
Do the parts share nothing?: Divide and conquer

Graphs carry every one of these strategies, from greedy shortest paths to dynamic programming over edges. Graph Traversal, the next topic, starts with the two searches the rest of graph algorithms is built on.

← → move through sections and cards