Card 01/ 07
Choosing a Design Strategy by the Shape of the Subproblems
Whether subproblems overlap, whether one choice is always safe, and whether every candidate must be seen pick the strategy.
Divide and conquer, dynamic programming, greedy algorithms and backtracking all solve a problem through smaller problems, and which one fits is decided by how those smaller problems behave. This card names the four properties that tell them apart and puts them in the order to check them, as a decision you can run against a new problem.
A subproblem is a smaller instance of the same question: sorting half the array, the fewest coins for a smaller amount, the best schedule for the meetings that remain. Four questions about them decide the strategy. Must the answer list every candidate, or only report the best one or a count? Can one choice at each step be proved always safe? Does the same subproblem come up more than once? Do the parts share nothing, so each can be solved alone and the answers combined?
When Every valid candidate must be listed, not only the best one or how many there are
, chooseWhen One choice at each step can be proved safe by an exchange argument
, chooseWhen The same smaller problem recurs, and the answer is a best value or a count
, chooseWhen The input splits into parts that share nothing, and their answers combine
, choose
Otherwise No property is clear yet: write the backtracking search over the choices, then memoise it if its states repeat, as Memoising a Backtracking Search Whose States Repeat shows.
The order matters, because a problem can have more than one of these properties and the first that holds wins. Listing every candidate comes first because nothing else can do it: a table or a greedy rule keeps one answer per subproblem, and a full list of 22,310 sets takes at least 22,310 steps however it is found. Greedy comes before dynamic programming because, where its proof holds, it solves the same subproblems more cheaply, making one choice where a table tries them all. The proof is the condition, not the look of the rule: a rule that only seems right falls through to dynamic programming, as Trusting a Greedy Rule Without a Proof shows. Divide and conquer is last because parts that share nothing are what remain once the overlapping case is taken.
Two boundaries are easy to blur. Greedy and dynamic programming can face the same subproblems; the difference is a proof that one choice is safe. Dynamic programming and divide and conquer both recurse; the difference is whether a subproblem recurs. Merge sort's halves never meet again, while computing Fibonacci numbers asks for the same values many times over.
When none of the four is clear, the fallback is the search that tries every choice, with its states then checked for repeats. Memoising a Backtracking Search Whose States Repeat shows that search turning into dynamic programming.
← → move through sections and cards