optimal substructure

The property that an optimal solution to a problem is built from optimal solutions to its subproblems.

In more detail

A shortest path from A to C through B contains a shortest path from A to B. Both greedy algorithms and dynamic programming need it; DP adds overlapping subproblems and greedy adds the greedy-choice property.

Related terms

Taught in

References