Elements of DP & proving optimal substructure

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 = \Theta(n^2)$. Matrix-chain: $n^2 \times n = \Theta(n^3)$. LCS: $mn \times 1 = \Theta(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 $\Theta(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=\Theta(n^2)$ edges $\Rightarrow \Theta(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.