Choosing a Design Strategy

Choosing a design strategy means reading a problem's subproblems. The topic opens on four questions about them, asked in order: must every candidate be listed, can one choice be proved safe, do subproblems recur, and do the parts share nothing. Two examples then move a problem from one strategy to another: a failing greedy coin rule becomes a table over amounts, and a backtracking search for dishes becomes dynamic programming once its repeating states are memoised. A comparison sets the four strategies side by side on subproblems, choices and cost, and a gotcha counts the hits of a memo on merge sort, where nothing repeats. An exercise names the strategy for four problems.