Dynamic programming needs optimal substructure and overlapping subproblems. Give a problem that has the first and not the second, a problem that has both, and say what each condition buys you.

Dynamic programming needs optimal substructure and overlapping subproblems. Give a problem that has the first and not the second, a problem that has both, and say what each condition buys you.

Approach: Separate the two conditions. One licenses building an optimum out of the optima of parts; the other is what makes storing those parts pay.

Merge sort has optimal substructure and no overlapping subproblems, the longest common subsequence has both, and the shortest path with negative cycles has neither. Optimal substructure says an optimal solution is built from optimal solutions of its parts, which is what licenses the recurrence at all; without it the recurrence is wrong rather than slow, which is why the longest simple path in a general graph has no dynamic program. Overlapping subproblems is the separate claim that the recursion tree revisits the same state many times, and it is the only thing memoization buys: merge sort splits into two disjoint halves that never recur, so a memo table adds bookkeeping and saves nothing, while the longest common subsequence on strings of length m and n touches only m*n distinct states inside an exponential recursion tree and collapses to O(m*n). The practical test is to count distinct states against the size of the recursion tree: when the two are the same order, plain recursion is already optimal.

Follow-up: Which of the two conditions does a greedy algorithm additionally require, and what is that extra condition called?

Key concepts: optimal substructure, overlapping subproblems, memoization, recursion tree, merge sort.