Optimal substructure a principle How to find the optimal substructure a Keep the sub-problem space as simple m Make a choice to split the problem into one or more sub-problems ■ Just assume a choice with such a choice, you should determine the space of sub-problems a Prove your choice is optimal by cut and paste Two factors Which problems is suitable? ms are nv a Shortest path in a graph ptimal solution? a Longest path in a graph a How many choices you should determine which sub-problems should be used in an optimal solution? 清华太学未证想 Overlapping sub-problems Reconstructing an optimal solution a Need some other information to constructing the optimal solution, generally e choice of the sub-problems7 清华大学 宋斌恒 37 Optimal substructure n How to find the optimal substructure n Make a choice to split the problem into one or more sub-problems n Just assume a choice n With such a choice, you should determine the space of sub-problems. n Prove your choice is optimal by cut and paste technique. 清华大学 宋斌恒 38 A principle n Keep the sub-problem space as simple as possible! 清华大学 宋斌恒 39 Two factors n How many sub-problems are involved in an optimal solution? n How many choices you should determine which sub-problems should be used in an optimal solution? 清华大学 宋斌恒 40 Which problems is suitable? n Shortest path in a graph n Longest path in a graph 清华大学 宋斌恒 41 Overlapping sub-problems n Is the way to reduce the computation 清华大学 宋斌恒 42 Reconstructing an optimal solution n Need some other information to reconstructing the optimal solution, generally, the choice of the sub-problems