Optimal Substructure

Optimal substructure is the reason a recurrence is safe. It says that once you choose how the larger solution connects to smaller states, the smaller pieces should themselves be optimal for their states. If a smaller piece were not optimal, replacing it with a better one would improve the larger answer, contradicting optimality.

For House Robber, if you decide to rob house i, the remaining left side must be the best answer through i - 2. A worse left answer would never be part of the best total. For Edit Distance, after choosing insert, delete, or replace, the remaining prefix problem must be solved optimally.

Shortest path in an unweighted graph has optimal substructure: the shortest path to a node contains shortest paths to intermediate nodes. Minimum Path Sum has it because the cheapest path to a cell must extend the cheaper of the two best paths into its parents. Coin Change has it because after taking one coin, the rest of the amount should be solved with the fewest coins possible.

Counting DPs also use a related form of compositional structure. In Climbing Stairs, the number of ways to reach i is the sum of complete counts for i - 1 and i - 2. The subanswers are not optimal in a min or max sense, but they are still reusable complete answers.

Some problems appear to lack optimal substructure only because the state is missing information. Suppose a path problem charges a penalty based on the previous two moves. A state that stores only the current cell may be insufficient, because the best continuation depends on recent direction history. Add that history to the state, and optimal substructure may return.

Other problems truly resist simple DP because local optimal subsolutions are incompatible globally. If choosing the best part for one segment prevents a feasible choice in another segment and the constraint is not captured by the state, combining individually optimal pieces can be wrong.

A strong DP explanation includes a short exchange argument. State the final decision, identify the remaining subproblem, and explain why that remaining subproblem must be optimal. For a minimum recurrence, say that if the remaining piece were not minimum, swapping in the minimum piece would produce a better total. For a maximum recurrence, use the symmetric argument.

This proof does not need to be formal, but it must connect the recurrence to correctness. Interviewers care that you are not just copying a familiar formula.