Jump to content

Optimal substructure

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Poor Yorick (talk | contribs) at 04:10, 10 June 2003. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

In computer science, the Optimal-substructure property refers to problems with optimal solutions that exhibit optimal solutions in its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms in a problem.

An example of Optimal-substructure includes the fact that if a subproblem Sab has an activity Py, then it should contain optimal solutions to subproblems Say and Syb.

  • TODO: Add Recursion, misc.

An optimal substructure problem is the longest-common subsequence problem.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Optimal_substructure&oldid=6363787"