What is Optimal Substructure ?

Optimal Substructure is global optimal that constructed from optimal solution of every subproblems. For example, to find the shortest path of graph below; first we need to calculate every sub-path from S to G, then collect any shortest sub-path to create complete shortest path.

Figure 1 Find Shortest Path of A Graph Using Optimal Substructure

There is three stpes to solve a problem using Optimal Substructure:

1. Break down a problem become smaller subproblems.
2. Find the optimal solution for every subproblem recursivly.
3. Collect every optimal solution to build complete optimal soultion.

To solve graph above, we need break down the problem into two subproblems. First subproblem or sub-path represented by non-dashed line, and second subproblem represented by dashed line. Then we calculate every distance in every subproblem scope. After that, we can find the shortest distance in every subproblem. Finally, we collect every shortest sub-path to create full shortest path.