Optimal Substructure

Optimal Substructure is the property that an optimal solution to a problem contains within it optimal solutions to subproblems. It is the formal backbone of dynamic programming and greedy algorithms, and it is far rarer in real systems than textbook treatments suggest. Most interesting problems — in economics, biology, and social systems — exhibit path dependence, feedback loops, and non-decomposable interactions that violate the independence assumption required for optimal substructure. The prevalence of this property in algorithmic textbooks reflects not the structure of reality but the structure of problems we have learned to solve: we define problems to have optimal substructure because our tools require it, not because nature obliges.