最优子结构（Optimal Substructure） 最优子结构的存在是应用动态规划的前提（或者说必要条件），由此可以避免重复计算； 1. 图算法 最短路径的子路径也一定是最短的； 简单地反证，如果最短路径的中间两点，之间的路径不是最短路径的话，那么一定存在其他的最短路径，最终使得当前的起点到终点的最短路径其实不是最短路径