动态规划| DP-2中的最优子结构性质

正如我们在 第一组 ，以下是一个问题的两个主要性质，它们表明给定的问题可以用动态规划来解决： 1） 重叠子问题 2） 最优子结构

我们已经在中讨论了重叠子问题的性质 第一组 .让我们在这里讨论最优子结构性质。

2） 最佳子结构： 如果给定问题的最优解可以通过其子问题的最优解得到，则该问题具有最优子结构性质。

例如，最短路径问题具有以下最优子结构特性： 如果节点x位于从源节点u到目标节点v的最短路径中，那么从u到v的最短路径是从u到x的最短路径和从x到v的最短路径的组合 弗洛伊德-沃沙尔 负权边的单源最短路径算法 贝尔曼-福特 是动态规划的典型例子。

另一方面，最长路径问题不具有最优子结构性质。这里所说的最长路径是指两个节点之间最长的简单路径（没有循环的路径）。考虑下面给出的未加权图 CLRS手册 .从q到t有两条最长的路径：q→R→t和q→s→t、 与最短路径不同，这些最长路径不具有最优子结构特性。例如，最长路径q→R→t不是从q到r的最长路径和从r到t的最长路径的组合，因为从q到r的最长路径是q→s→T→从r到t的最长路径是r→Q→s→T

我们将在以后的文章中讨论一些示例问题 动态规划 .

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

参考资料： http://en.wikipedia.org/wiki/Optimal_substructure CLRS手册