在分而治之方法中，子问题彼此独立。
因此，无法利用重叠的子问题。
最佳子结构状态的CLRS定义：
“如果问题的最佳解决方案中包含子问题的最佳解决方案，那么问题将表现出最佳子结构。”
我们是否知道使用分而治之的方法解决子问题是最佳的？如果是这样，我认为最优的子结构适用于分治法。
分而治之会利用最佳子结构吗？
•
问答
gaipeidong 回答：分而治之会利用最佳子结构吗？
是的。向自己证明的速度非常快。
给定一个具有分治解法的算法，假设它没有最优子结构。我会做一些简单的记号：P 是整体问题，PL 和 PR 是左右子问题。 S(P) 是 P 的解。
根据分治解的定义，要求 S(P) = S(PL) + S(PR)，其中 + 是子问题解的重组。
根据已知没有最优子结构的问题的定义，不一定是 S(P) = S(PL) + S(PR)。
这与定义直接矛盾。假设与给定相矛盾，所以假设一定是错误的。
你可以切换给定和假设得到同样的矛盾。
所以说一个问题有一个最优子结构相当于说这个问题有一个分而治之的解决方案。