Optimal substructure is something we already covered when we introduced greedy algorithms. Recall that a problem exhibits optimal substructure, if an optimal solution to the problem contains within it, the optimal solutions to the sub-problems. There's a common pattern when trying to discover optimal substructure for a problem that can be explained as follows:

• Show that a solution to the problem consists of making a choice, which leaves one or more subproblems to be solved. This choice may not be obvious and it is likely that many choices have to be tried (contrary to a greedy approach, in which a single optimal choice is made).
• Supposing that you are given the choice that leads to an optimal solution, determine the subproblems that follow.

• Show that the solutions to the subproblems used within an optimal solution to the problem must themselves be optimal
• Usually, a cut-and-paste technique is used here. By supposing that each subproblem solution is not optimal, if a non-optimal solution is cut out and an optimal one is pasted in, a better solution to the original problem is produced, contradicting the supposition that the original solution to the problem was optimal