迅速理解 LCS 最长公共子序列问题
在算法与数据结构的经典问题中，最长公共子序列（Longest Common Subsequence，简称 LCS）问题占据着重要的地位。给定两个序列，我们需要找到它们最长的公共子序列，而子序列要求保持原序列元素的顺序但不需要连续。LCS 问题在文本比较、生物信息学中的基因序列比对等领域有着广泛的应用。例如，对于序列 X = "ABCBDAB" 和序列 Y = "BDCABB"，它们的最长公共子序列为 "BCAB"，长度为4。
LCS 的标准解法可以通过动态规划在相对高效的时间内解决，但在某些特殊情境下，我们可以通过巧妙的转化进一步优化其效率，尤其当其中一个序列中元素不重复时。
动态规划
动态规划是解决 LCS 问题的标准方法。设序列 $ X $ 和序列 $ Y $ 的长度分别为 $ m $ 和 $ n $。我们定义二维数组 $ dp $ 为 $ X $ 的前 $ i $ 个元素和 $ Y $ 的前 $ j $ 个元素的最长公共子序列长度，则状态转移方程为：
[*]若 $ X = Y $，则 $ dp = dp + 1 $；
[*]还可从之前状态取，$ dp = \max(dp, dp) $。
每一个 $ dp $ 都可直接得出，时间复杂度 \(O(mn)\)。
每一个 $ dp $ 仅由 $ dp$ 推出，通过滚动数组或交替数组的技巧，将空间复杂度降低至 $ O(\min(m,n)) $。具体实现时，仅维护当前和上一行（或列）的信息即可。
代码略。
无重复元素的 LCS 问题
当问题中有额外的限制条件时，我们常能发现优化的可能性。具体而言，当序列 $ X $ 中的元素是唯一的，即每个元素至多出现一次时，LCS 问题可转化为最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题，从而实现高效求解。
具体转化过程为：
[*]建立序列 $ Y $ 中元素到其索引位置的映射；
[*]用序列 $ X $ 中的元素依次检查该元素是否存在于 $ Y $ 中，若存在，则用其在 $ Y $ 中的位置替代；
[*]形成新的序列 $ Z $，序列 $ Z $ 中的每个元素均为序列 $ Y $ 中的索引位置。
转化后问题变为寻找序列 $ Z $ 的 LIS。该转化之所以成立，其正确性源于如下两个核心事实：
[*]保序性：原LCS要求序列顺序匹配，这与转化后的序列 $ Z $ 中元素位置索引的严格递增特性一致。
[*]唯一性保证映射的单射性：由于序列 $ X $ 中出现，一定只能出现在唯一的位置， 中元素的唯一性，映射过程中不会出现元素位置的歧义，确保新序列 $ Z $ 能够精确代表 $ X $ 和 $ Y $ 的顺序关系。
由于 $ Y $ 中元素，若在 $ X $ 中出现，一定只能出现在唯一的位置，所以可以把 $ Y $ 转化为索引，求“索引的递增序列”，一个递增的索引序列就代表一个公共子序列。
因此，此转化将原本朴素的 LCS 问题优化为 $ O(m \log m) $ 的 LIS 问题，使得在特定场景下的算法效率大大提高。LIS 的代码实现可以参考往期文章。
int main() {
int n;
cin >> n;
vector<int> a(n), tail;
unordered_map<int, int> mp;
mp.reserve(n);
for (int i = 0; i < n; i++) {
Cin >> a;
mp] = i;
}
for (int i = 0; i < n; i++) {
int x;
Cin >> x;
if (!mp.count(x)) continue;
x = mp;
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) {
tail.push_back(x);
} else {
*it = x;
}
} printf("%d\n", tail.size());
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 感谢分享 这个好，看起来很实用 新版吗？好像是停更了吧。 谢谢分享，辛苦了 收藏一下 不知道什么时候能用到 谢谢分享，试用一下 谢谢分享，试用一下 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享，学习下。 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 鼓励转贴优秀软件安全工具和文档！ 谢谢楼主提供！ 感谢发布原创作品，程序园因你更精彩 不错，里面软件多更新就更好了 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享，下载保存了，貌似很强大 东西不错很实用谢谢分享 感谢，下载保存了 收藏一下 不知道什么时候能用到
页:
[1]
2