将最长公共子序列降为最长递增子序列

Question

在最多一个序列存在重复的情况下，可以将最长公共子序列问题转化为最长递增子序列问题。减少问题的过程说明在这里：

假设您有以下序列：

S1 = {D, B, A, C, E}
S2 = {E, Z, X, D, A, Y, C}

然后，创建一个整数序列S3，其中您必须将S2的每个元素的位置放在S1中（如果元素在S1中不存在，那么忽略那个元素）。在本例中：

S3 = {4, 0, 2, 3}
// Z, X and Y in S2 where ignored

这种方法是如何工作的？为什么这种约简解决了寻找最长公共子序列的问题？

Answer 1

给定您如何构建S3，您可以保证S3的元素指向“仅且全部”S1和S2的公共元素。

通过使用这些位置并找到最长的递增子序列，您可以确保找到的是原始S1和S2的子序列，而不仅仅是它们共有的元素的数目：

• 它将是S1的子序列，因为S3中元素的数值编码了S1中的位置，所以S3的增子序列=S1的子序列
• 它将是S2的子序列，因为S3元素中编码的元素与S2元素的顺序相同，所以S3的子序列=S2的子序列

因此，S3最长的递增子序列将“编码”：

• S1的子序列
• S2的子序列
• 只包含S1和S2中存在的元素的序列
• 这类子序列中最长的

即S1和S2之间的最长公共子序列