Optimal-substructure

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 S_ab has an activity P_y, then it should contain optimal solutions to subproblems S_ay and S_yb.

• TODO: Add Recursion, misc.

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