Example
Consider finding aDefinition
A slightly more formal definition of optimal substructure can be given. Let a "problem" be a collection of "alternatives", and let each alternative have an associated cost, ''c''(''a''). The task is to find a set of alternatives that minimizes ''c''(''a''). Suppose that the alternatives can be partitioned into subsets, i.e. each alternative belongs to only one subset. Suppose each subset has its own cost function. The minima of each of these cost functions can be found, as can the minima of the global cost function, ''restricted to the same subsets''. If these minima match for each subset, then it's almost obvious that a global minimum can be picked not out of the full set of alternatives, but out of only the set that consists of the minima of the smaller, local cost functions we have defined. If minimizing the local functions is a problem of "lower order", and (specifically) if, after a finite number of these reductions, the problem becomes trivial, then the problem has an optimal substructure.Problems with optimal substructure
*Problems ''without'' optimal substructure
* Longest path problem * Addition-chain exponentiation * ''Least-cost airline fare.'' Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D. However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure. The cheapest flight from A to B that involves at most ''k'' layovers is either the direct flight; or the cheapest flight from A to some airport C that involves at most ''t'' layovers for some integer ''t'' with ''0≤tSee also
* Dynamic Programming * Principle of optimality *References