liveBook · Manning

Optimal substructure

As explained in Timeless Algorithms, The Foundational Ideas

The principle of optimality is the property that an optimal strategy can be formed from optimal decisions for the remaining stages after any state.

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

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines the property and demonstrates it through smaller states and a knapsack recurrence, alongside the separate requirement of overlapping subproblems.
Examples
Illustrates the property with 0/1 knapsack, shortest routes, and inventory control.
What you can do after
Evaluate whether smaller optimal solutions can support a dynamic programming formulation for a decision problem.
How it connects
Connects optimal substructure to dynamic programming, overlapping subproblems, recurrence relations, and sequential decision-making.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.