迅速理解 LCS 最长公共子序列问题

在算法与数据结构的经典问题中，最长公共子序列（Longest Common Subsequence，简称 LCS）问题占据着重要的地位。给定两个序列，我们需要找到它们最长的公共子序列，而子序列要求保持原序列元素的顺序但不需要连续。LCS 问题在文本比较、生物信息学中的基因序列比对等领域有着广泛的应用。
例如，对于序列 X = "ABCBDAB" 和序列 Y = "BDCABB"，它们的最长公共子序列为 "BCAB"，长度为4。
LCS 的标准解法可以通过动态规划在相对高效的时间内解决，但在某些特殊情境下，我们可以通过巧妙的转化进一步优化其效率，尤其当其中一个序列中元素不重复时。
动态规划

动态规划是解决 LCS 问题的标准方法。设序列 $ X $ 和序列 $ Y $ 的长度分别为 $ m $ 和 $ n $。我们定义二维数组 $ dp[j] $ 为 $ X $ 的前 $ i $ 个元素和 $ Y $ 的前 $ j $ 个元素的最长公共子序列长度，则状态转移方程为：

• 若 $ X = Y[j] $，则 $ dp[j] = dp[i-1][j-1] + 1 $；
  
• 还可从之前状态取，$ dp[j] = \max(dp[i-1][j], dp[j-1]) $。
  

每一个 $ dp[j] $ 都可直接得出，时间复杂度 \(O(mn)\)。
每一个 $ dp[j] $ 仅由 $ dp[i-1]$ 推出，通过滚动数组或交替数组的技巧，将空间复杂度降低至 $ 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 的代码实现可以参考往期文章。

1. int main() {
2.     int n;
3.     cin >> n;
5.     vector<int> a(n), tail;
7.     unordered_map<int, int> mp;
8.     mp.reserve(n);
9.        
10.     for (int i = 0; i < n; i++) {
11.         Cin >> a[i];
12.         mp[a[i]] = i;
13.     }
14.     for (int i = 0; i < n; i++) {
15.         int x;
16.         Cin >> x;
17.         if (!mp.count(x)) continue;
18.         
19.         x = mp[x];
21.         auto it = lower_bound(tail.begin(), tail.end(), x);
22.         if (it == tail.end()) {
23.             tail.push_back(x);
24.         } else {
25.             *it = x;
26.         }
27.     } printf("%d\n", tail.size());
28. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！