问题描述
如果最多一个序列具有重复，我们可以将最长公共子序列问题减少为最长增加子序列问题.在此处中说明了减少问题的过程:
这种方法如何起作用?为什么这种减少解决了找到最长的公共子序列的问题?
鉴于如何构建S3，可以确保S3的元素指向仅且全部" S1和S2的共同元素.
通过使用位置并找到最长的增加子序列，可以确保所找到的将是原始S1和S2的子序列，而不仅仅是它们共同的元素数量:
- 这将是S1的子序列，因为S3中元素的数值编码了S1中的位置，因此S3的递增子序列= S1的子序列
- 它将是S2的子序列，因为在S3的元素中编码的元素与S2的元素的顺序相同，因此S3的子序列 = S2的子序列
因此，S3增长最快的子序列将编码":
- S1的子序列
- S2的子序列
- 仅包含S1和S2中都存在的元素的序列
- 此类子序列中最长的
即S1和S2之间最长的公共子序列
您可以使用上述过程解码"，即以index = S3的元素获取S1的元素.
注意:如链接中所指出的，仅在最多一个序列具有重复的情况下才有效，而构建S3时，您应将没有重复的序列作为S1.
这似乎是更常见的将LIS还原为LCS 的逆序./p>
We can reduce the Longest Common Subsequence problem to Longest Increasing Subsequence problem if at most one sequence has repetitions. The process of reducing the problem is explained here:
How does this approach work? Why does this reduction solve the problem of finding the longest common subsequence?
Given how you build S3, you are guaranteed that the elements of S3 point to "only and all" the common elements of S1 and S2.
By using the positions and finding the longest increasing subsequence you make sure that what you find will be a subsequence of the original S1 and S2 and not just the number of elements they have in common:
- It will be a subsequence of S1 because the numerical value of the elements in S3 encode the positions in S1, so increasing subsequence of S3 = subsequence of S1
- It will be a subsequence of S2 because the elements encoded in the elements of S3 are in the same order as the elements of S2, so subsequence of S3 = subsequence of S2
Therefore, the longest increasing subsequence of S3 will "encode":
- a subsequence of S1
- a subsequence of S2
- a sequence that contains only elements present in both S1 and S2
- the longest of such subsequences
i.e. the longest common subsequence between S1 and S2
Which you can "decode" by using the process described, i.e. take the elements of S1 with index = element of S3.
NOTE: as pointed out in the link, this only works when at most one of the sequences has repetitions, and when building S3 you should take the sequence without repetitions as S1.
This seems like the inverse of the more common reduction of LIS to LCS.
这篇关于将最长的公共子序列减少到最长的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！