Solutions built from smaller solutions
A problem exhibits optimal substructure when an optimal solution to the whole problem is composed of optimal solutions to its subproblems. This property is the foundation that both greedy algorithms and dynamic programming rely on.
A concrete sense of it
Consider the shortest path from a start to a goal that passes through some intermediate city. If the full path is shortest overall, then the portion from the start to that intermediate city must itself be a shortest path. If it were not, you could substitute a shorter piece and get a shorter overall path, a contradiction.
- The whole answer decomposes into subproblem answers.
- Each piece must itself be optimal, or the whole could be improved.
Why it is not automatic
Optimal substructure can fail. The longest simple path problem lacks it, because stitching two longest paths together may reuse a vertex and break the simple path constraint. Before applying dynamic programming, you should argue, often by a cut and paste exchange, that an optimal whole really does contain optimal parts.
Key idea
Optimal substructure means an optimal solution is assembled from optimal subproblem solutions; verifying it, usually by a cut and paste argument, is the precondition for greedy and dynamic programming methods.