动态规划最优子结构的证明

动态规划最优子结构的证明可以通过数学归纳法来进行。假设我们有一个问题P，它可以被分解为若干个子问题P1，P2，...，Pk。我们假设对于每个子问题Pi，它的最优解已经被求解出来了。

现在我们来证明问题P的最优解是否包含了子问题的最优解。

首先，我们假设问题P的最优解为S，而子问题Pi的最优解为Si。我们假设问题P的最优解S不包含子问题Pi的最优解Si。

如果S不包含Si，那么我们可以通过将Si替换为S中对应的部分来得到一个更优的解S'。这是因为Si是Pi的最优解，所以将Si替换为S中对应的部分不会影响其他子问题的最优解。因此，S'比S更优，这与S是问题P的最优解相矛盾。

因此，我们可以得出结论：问题P的最优解必然包含了子问题的最优解。

这就证明了动态规划最优子结构的性质。