Elements of DP & proving optimal substructure

The cut-and-paste proof, the subproblem-graph running-time view, and a cautionary non-example (longest simple path).

Proving optimal substructure: cut-and-paste

Before you trust a DP recurrence you must prove the problem has optimal substructure. The standard tool is the cut-and-paste argument (a proof by contradiction):

> Suppose an optimal solution $S$ to the whole problem uses a suboptimal solution $S^{'}$ to some subproblem. "Cut out" $S^{'}$ and "paste in" the optimal subproblem solution $S^{' *}$ . Because $S^{' *}$ is at least as good as $S^{'}$ , the resulting whole solution is at least as good as $S$ — and the subproblem is independent, so the paste is legal. This contradicts $S$ being optimal. Therefore the subproblem solution inside $S$ was optimal.

Rod cutting, concretely. If the optimal cut of a length- $n$ rod left a length- $(n - i)$ remainder cut suboptimally, replacing that remainder's cut with the optimal one raises total revenue — contradiction. Hence the remainder is cut optimally, which is exactly what the recurrence $r_{n} = max_{i} (p_{i} + r_{n - i})$ assumes.

Two dials of optimal substructure

Problems differ along two axes, and their product estimates the running time:

How many subproblems an optimal solution uses: rod cutting uses 1 (the remainder); matrix-chain uses 2 (left and right of a split).
How many choices you weigh: rod cutting has $n$ (first-cut position); matrix-chain has $j - i$ (split point); LCS has $O (1)$ .

Running time $\approx$ (\#subproblems) $\times$ (\#choices). Rod: $n \times n = Θ (n^{2})$ . Matrix-chain: $n^{2} \times n = Θ (n^{3})$ . LCS: $mn \times 1 = Θ (mn)$ .

The subproblem graph makes it precise

Make a directed graph: a vertex per distinct subproblem, an edge for each dependency (each choice that points to a smaller subproblem). Then the bottom-up running time is $Θ (V + E)$ — and the correct bottom-up fill order is a reverse topological sort of this graph (solve the things-you-depend-on first). Rod cutting: $V = n$ vertices, $E = Θ (n^{2})$ edges $\Rightarrow Θ (n^{2})$ .

A non-example: longest simple path

Not every problem has optimal substructure. Shortest path does: if $u \to w \to v$ is shortest, then $u \to w$ and $w \to v$ are each shortest, and they share no vertices but $w$ — the subproblems are independent.

Longest simple path does not. Consider $q \to r \to t$ with extra edges. The longest simple $q \to t$ might be $q \to r \to t$ , yet $q \to r$ alone is not the longest simple $q$ -to- $r$ path (a longer one detours through other vertices). The subpaths compete for the same vertices — they are not independent — so you cannot glue independently optimal subpaths. (Indeed, longest simple path is NP-complete; no polynomial DP is known.)

The lesson: optimal substructure secretly requires independent subproblems. Always check independence before writing the recurrence.

The three paradigms on the axes that actually separate them. Divide-and-conquer recurses on disjoint pieces, so a table buys nothing. DP and greedy both need optimal substructure; the difference is that DP makes its choice after solving the subproblems, while greedy commits before.

The non-example, drawn. A longest simple path q to t is q → r → t, yet its subpath q → r is not a longest q-to-r path — the dashed route q → s → t → r is longer. The two candidates fight over the vertices r and t, so the subpaths are not independent and cannot be glued. No optimal substructure, no DP.