Encyclopedia > Optimal-substructure

  Article Content


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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Ayurvedic medicine

... elements ether and air), Pitta (fire), and Kapha[?] (water and earth). Ayurveda is described in the Rig Veda and is still in use today, especially ...