最优合并问题的最优子结构性质的证明使用反证法

我们假设最优合并问题不满足最优子结构性质，即存在一种不是最优的合并方案。

设有两个已经按升序排好序的序列S1和S2，它们的长度分别为m和n。设它们的最优合并方案为M1，其中M1包括了这两个序列的所有元素，并且合并后的序列按升序排列。现在假设存在一种不是最优的合并方案M2，其中M2也包括了S1和S2的所有元素，但是合并后的序列不是按升序排列的。

由于M1是最优的，因此M2的总代价必须大于M1的总代价。我们设M1的总代价为C1，M2的总代价为C2。

根据假设，M2的合并结果不是按升序排列的，因此必然存在一对相邻元素a和b，满足a在S1中，b在S2中，且a>b。

现在我们考虑把M2中的a和b交换，得到一个新的合并方案M3。显然，M3包括了S1和S2的所有元素，并且合并后的序列也是按升序排列的。因此，M3的总代价必然小于或等于M2的总代价。

现在我们来比较M1和M3的总代价。由于M1和M3的合并结果都是按升序排列的，因此它们的总代价只与它们包含的元素个数有关。而M3包含的元素个数是和M1相同的，因此M1和M3的总代价也相同。

综上所述，我们得到了一个矛盾：M2的总代价大于M1的总代价，而M3的总代价小于或等于M2的总代价，但是M3和M1包含的元素个数相同，因此它们的总代价也应该相同。这个矛盾说明我们的假设是错误的，即不存在一种不是最优的合并方案。因此，最优合并问题具有最优子结构性质。

相关问题

最优合并问题的最优子结构性质证明，反证法

假设最优合并问题没有最优子结构性质，则存在某个最优解 S，它的其中一个子序列 T 也是最优解，但是在 S 中，T 不是相邻的两个序列合并得到的。

考虑将 S 分为两个部分，一部分包含 T，另一部分是剩余的序列。设这两部分分别为 A 和 B，即 S = A + B。

因为 T 在 S 中是最优解，所以 A 和 B 各自也是最优解。因为 T 不是相邻的两个序列合并得到的，所以 T 一定被分成了两个部分，设这两部分分别为 T1 和 T2，即 T = T1 + T2。

现在考虑将 A 和 B 合并成一个序列。由于 T1 和 T2 不相邻，所以在将 A 和 B 合并的过程中，T1 和 T2 也不会相邻。因此，在合并 A 和 B 的过程中，可以将 T1 和 T2 分别插入到 A 和 B 中，从而得到一个新的最优解 S'。但是，由于 T1 和 T2 不相邻，所以 S' 肯定比 S 更优，这与 S 的最优性矛盾。因此，假设不成立，最优合并问题具有最优子结构性质。

最优合并问题的最优子结构性质证明

最优合并问题是指给定 n 个已经排好序的序列，将它们合并成一个序列，使得总的比较次数最少。最优合并问题的最优子结构性质可以用归纳法证明。

假设我们已经找到了将 k 个序列合并成一个序列的最优方案，那么我们考虑将 k+1 个序列合并成一个序列的最优方案。假设这 k+1 个序列分成两组，前面 k 个序列已经排好序，而第 k+1 个序列需要和前面的 k 个序列合并。我们可以将第 k+1 个序列插入到前面 k 个序列中的任意一个序列的后面，然后将这 k+1 个序列合并成一个序列。因为前面的 k 个序列已经排好序，所以将第 k+1 个序列插入到前面的序列中不会影响前面的序列的相对顺序。此时，总的比较次数等于将前面的 k 个序列合并成一个序列的比较次数加上将第 k+1 个序列插入到前面的 k 个序列中的任意一个序列的后面所需的比较次数。因此，将 k+1 个序列合并成一个序列的最优方案可以通过将第 k+1 个序列插入到前面 k 个序列中的任意一个序列的后面，并找到将前面的 k 个序列合并成一个序列的最优方案来得到。因此，最优合并问题具有最优子结构性质。