Optimal substructure

In computer science, a problem is said to have optimal substructure if its optimal solution can be constructed efficiently from optimal solutions to its subproblems. This property is used to determine the usefulness of dynamic programming and greedy algorithms in a problem.

An example of optimal substructure, finding a shortest path between two vertices in a graph, is shown in Figure 1. We first find the shortest path to the goal from all neighbors of the starting point (using the same procedure recursively), and then choose the overall path that minimizes the total edge weight.

Typically, a greedy algorithm is used to solve a problem with optimal substructure wherever such an algorithm can be found; otherwise, providing the problem exhibits overlapping subproblems as well, dynamic programming is used. If there are no greedy algorithms or overlapping subproblems, often a straightforward search of the solution space is the best possible solution.

Problems with optimal substructure

• Longest-common subsequence problem.