A sequence of decisions may be difficult to optimize as a whole, but its remaining stages can sometimes be solved as smaller problems. Optimal substructure is the property that an optimal overall solution can be constructed from optimal solutions to its constituent subproblems. Bellman’s principle of optimality expresses this idea for decisions made from a state onward. section 6.1.1 section 6.2.2
Optimal substructure supports dynamic programming, but it is distinct from overlapping subproblems. The former permits optimal smaller solutions to be combined; the latter means the same subproblems recur, so their solutions can be stored and reused. Without both properties, dynamic programming provides no meaningful advantage in this framework. section 6.1.1
0/1 knapsack
Let V(i, c) be the maximum value obtainable from the first i items with capacity c. For an item of value vᵢ and weight wᵢ, exclusion gives V(i − 1, c). If wᵢ ≤ c, inclusion gives vᵢ + V(i − 1, c − wᵢ). The recurrence selects the larger value; if the item is too heavy, exclusion is the only option. Each alternative relies on an optimal solution to a smaller state. section 6.2.1 section 6.2.2
The same structure appears in other decision problems:
- Shortest routes: a shortest route contains shortest routes between points along its path. A recurrence compares the best known route with one passing through a newly considered intermediate node. section 6.4.3
- Inventory control: each order has an immediate cost and leads to a future inventory state. Combining that cost with the minimum future cost identifies the best decision over the remaining horizon. section 6.4.2
