求解最长公共子序列

ChenDaxiana · 2025-08-18 17:43:00 · 算法·理论

前置芝士

最长公共子序列的定义：两个序列长度最长的相同子序列，子序列是按照在原序列中出现顺序排序取出元素形成的序列。
P1341 最长上升子序列。
AT_dp_f LCS 暴力版

声明

将最长公共子序列称为 LCS，最长上升子序列称为 LIS。

给定序列 \{x_n\}=\{x_1,x_2,x_3···x_{n-1},x_n\}，\{y_n\}=\{y_1,y_2,y_3···y_{n-1},y_n\}，两序列的 LCS 为 \{z_n\} = \{z_1,z_2,z_3···z_{k-1},z_m\}。

暴力

使用 DP 枚举。

以序列的长度为阶段，枚举两个序列，我们考虑设状态 dp_{i,j} 表示子序列 \{x_i\}，\{y_j\} 的 LCS 的长度，\{z_k\}表示此时的 LCS。我们需要注意 dp_{i,j} 与 dp_{i-1,j-1},dp_{i-1,j},dp_{i,j-1} 的转移关系，以及 x_i 与 x_j 对前面转移关系的约束，因为这两个量的等量或不等关系决定了这两个元素是否在当前的 LCS 中，也是影响 dp_{i,j} 取值的。那么我们进行分类讨论！

若 x_{i}=y_{j}，那么 x_{i},y_{j} 在 dp_{i,j} 中，即 z_k=x_i=y_j，\{z_{k-1}\} 是 \{x_{i-1}\},\{y_{j-1}\}的一个 LCS。
若 x_{i}\neq y_{j}，那么 z_{k} \neq x_{i}，\{z_k\} 是 \{x_{i-1}\} 与 \{y_{j}\} 的一个 LCS。
若 x_{i}\neq y_{j}，那么 z_{k} \neq y_{j}，\{z_k\} 是 \{x_{i}\} 与 \{y_{j-1}\} 的一个 LCS。

上述结论可由反证法严格证明。

dp_{i,j}=\begin{cases} dp_{i-1,j-1}+1 &if &x_i=y_i\\dp_{i-1,j} &if &x_i\neq y_i &and &dp_{i-1,j-1}\geq dp_{i,j-1} \\ dp_{i,j-1} &if &x_i\neq y_j &and &dp_{i-1,j-1}<dp_{i,j-1} \\ \end{cases}

由于 2,3 行中的 x_i\ne y_j 是同时存在的,有

dp_{i,j}=\begin{cases} dp_{i-1,j-1}+1 &if &x_i=y_i\\ \max \{dp_{i-1,j},dp_{i,j-1}\} &if &x_i\neq y_i \end{cases}

此时算法时间复杂度是 O(n^2) 级别，对于 n\le 10^5 的数据无法全部通过。

转化

另辟蹊径。

注意条件是给定两个排列！由于 \forall a_i,\forall b_i\in[1,n] 且每个元素出现且仅出现一次。

所以我们可以构造序列 \{c_{n}\}，c_i 表示元素 b_i 在 \{a_n\} 中的出现位置 id，用代码表示就是 c[b[i]] = c[a[id]] = id ，我们举个例子。

n=6

\{x\}=\{5,1,3,2,6,4\}

\{y\}=\{1,5,3,2,6,4\}

\{c\}=\{2,1,3,4,6,5\}

例如对于 y_1=1，1 在 \{x\} 中的第 2 位出现，c_i=2，此时 x_{c_i} =x_{2}=y_1=1，y_1,x_2,c_1，也就是 y_i,x_{id=c_i},c_i 是一组对应，

注意 \{c\} 的元素组成的子序列 \{2,3,4,6\}，这是一个上升子序列，观察其在 \{y\}，\{x\} 的对应序列，\{y\} = \{\red{1}, 5, \red{3}, \red{2}, \red{4}, 6\}，

这里提供一个不严谨证明即可。 1. 判断公共序列与具体位置无关，只考虑对应元素相等，满足先后顺序。 2. 考虑 $\{c\}$ 中一个**上升子序列**的两个元素，满足 $c_i<c_j,i<j$，此时 $i\to id_1,j\to id_2$（这里表示**映射**关系），即存在 $x_{id_1}=y_i,x_{id_2}=y_j$，那么对应的元素 $y_i$ 出现在 $y_j$ 前，元素 $x_{id_1}$ 出现在 $x_{id_2}$ 前，满足 $1$ 中的条件。 3. 推而广之，我们就将求公共序列**转化**为求上升序列，当然是求**最长**上升子序列（LIS）。 ## 二分求 LIS 求 $\{c_n\}$ 的 LIS，且 $O(n^2)$ 及时间复杂度更高的方法是不合法的。还是考虑 DP，因为 LIS 中后续的数**必须大于**前一个数(请读者使用**反证法**自行证明)，令序列 $\{dp_n\}$ 中 $dp_i$ 表示长度为 $i$ 的上升子序列的最小末尾（最后一个数的最小值），序列的最后一个存在值的下标应当是 LIS 的长度（**重点！**）。请先思考上升子序列需要满足哪些条件！对于 $\forall c_i,\forall c_j,i<j,需要c_i<c_j$. 我们需要不断更新这个序列（数组），我们以 $i$（$[1,n]$）为阶段枚举。注意序列应当单调递增 $(1)$，我们枚举的顺序是 $1\to n$ $(2)$(以下**简称**性质 $(1),(2)$ )。由于 LIS 的长度未知，所以我们只关心 $dp_{i_{max}}$ 的存在性，说人话就是只需找到最后一个 $dp_i$ 的位置。首先将 $\{dp_n\}$ 全部值初始化为**正无穷**（不严谨说法）。我们每次只进行两个操作。 1. 取出当前 $c_i$，找到 $\{dp_n\}$ 中**第一个大于等于**它的数（这里就是**二分**），设这个数位置为 $pos\in[1,n]$，令 $dp_{pos} = c_i$。 2. 更新答案，$ans=\max\{ans,pos\}$. **简要说明** ：对于操作 $1$，我们取出 $c_i$ 利用了二分算法，即利用了性质 $(1)$，由于性质 $(2)$，操作时**天然**满足当前元素 $dp_{pos}$ 在 $dp_{pos-1}$ 之前，由于 $dp_{pos}$ 是**第一个大于等于**的数，所以 $dp_{pos-1}<c_i$，我们可以将 $c_i$ 接入 $dp_{pos-1}$ 所代表的最长公共子序列，我们保证了 $\{dp_{pos}\}$ 具有性质 $(1)$，同时保证了 LIS 一定被更新，也就是说找出了答案。那么我们便获取了 $dp_{pos}$ 的一个新的**不劣**的值。当然这里可以分类讨论，即 $dp_{pos}$ 有值与无值，但两种情况下只需同样的更新操作，所以该讨论是不必要的。我们回顾一下，首先考虑我们利用了性质 $(2)$，这个性质是我们构造的，不变的，合法;那么对于性质 $(1)$ 呢？可以看出我们只需要当前 $\{dp_k\}$ 保持性质 $(1)$ ，那么 $\{dp_{k+1}\}$ 同样保持性质 $(1)$，$\{dp_{k+2}\},\{dp_{k+3}\}···$ 也同理满足，那么只需保证 $\{dp_1\}$ 符合性质 $(1)$ 即可。那么 > $请循其本!（return$ $ back!）-庄子

显然只含一个元素的 \{dp_1\} 必然符合单调性，那么我们也就做完了！

总结

算法时间复杂度为 O(n\log{n})，足够通过本题。我们回顾本题，实际上该解法有一个特点，就是所设状态不在答案中，但这不妨碍我们利用问题的最优子结构做 DP，所以我认为洛谷题解区的贪心说法并不严谨。本文倾注了作者超过 5 小时的时间，也是个人认为对于该问题的最好解释（目前）了，希望给大家带来一些启发。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long//保险栓
const int N = 1e5 + 5;

struct node{
    int val,id;
}x[N],y[N];

int c[N],dp[N],n,ans = 0,o;
inline int read();//快读快写不必在意
inline void write(int x,bool op);
signed main(){
    n = read();
    for (int i=1; i<=n; i++) x[i].val = read(),x[i].id = i,c[x[i].val] = i;//构造 c 序列
    for (int i=1; i<=n; i++) y[i].val = read();
    memset(dp,0x77,sizeof dp);//初始化为无穷大
    dp[1] = c[y[1].val];
    int x,pos;
    for (int i=1; i<=n; i++){
        o = c[y[i].val];//取出 ci
        pos = lower_bound(dp+1,dp+n+1,o) - dp;//二分找,操作 1
        ans = max(ans,pos);//更新答案，操作 2
        dp[pos] = o;
    }
    write(ans,0);
    return 0;
}

//快读快写不必在意
inline int read(){
    int x = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x * f;
}
char rec[21];
inline void write(int x,bool op){
    if (x == 0){
        putchar('0');
        return ;
    }
    if (x < 0){
        x = -x;
        putchar('-');
    }
    int p = 0;
    while(x){
        rec[p++] = x % 10 + '0';
        x /= 10;
    }
    while(p--){
        putchar(rec[p]);
    }
    if (op){
        putchar(' ');
    }
}

特别鸣谢

@2011hym(本站同名)，好同学。

@Miracle_ZX 大佬，本文受到某篇启发。

完结撒花，制作不易，管理大大给个精品吧。