DP算法入门（3）

最长公共子序列

先上例题【模板】最长公共子序列

解题过程

$(1)$ 确定状态:

$dp[i][j]$ 表示 $x[\mathrm{1...}i]$ 和 $y[\mathrm{1..}j]$ 的最长公共子序列长度。

$(2)$ 状态转移：对于两个序列中的 $x_i$ 和 $y_j$ ，分成两种情况。

1.$x_i=y_j$(长度相等) ：

求解 $X_{i?1}$ 和 $Y_{j?1}$ 的最长公共子序列长度加一。

状态转移方程 $dp[i][j]=dp[i?1][j?1]+1$

2.$x_i\ne y_j$(长度不等)

可以去掉 $x_i$ , 求 $X_{i?1}$ 和 $Y_j$ 的最长公共子序列长度

或者去掉 $y_i$ , 求 $X_i$ 和 $Y_{j?1}$ 的最长公共子序列长度

状态转移方程 $dp[i][j]=max(dp[i?1][j],dp[i?1][j])$

$(3)$ 边界条件 $dp[i][0]=0,dp[0][j]=0$

$(4)$ 求解目标 $dp[x_i][y_j]$ , $x_i$ 和 $y_j$ 为字符串 $x,y$ 的长度。

伪代码

(50pts) 时间复杂度 $O(n^2)$

#include<bits/stdc++.h>
using namespace std;
int x[100005],y[100005];
int n,dp[1005][1005];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&x[i]);
	for(int i=0;i<n;i++)scanf("%d",&y[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(x[i-1]==y[j-1])dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
		}
	}
	printf("%d",dp[n][n]);
	return 0;
}

正常二分没有想出来，但是，我想到了另一种奇妙的做法，我们知道在最长上升子序列中，我们最后使用优化变成了 $O(nlo{g}_{2}n)$ 的做法。

我们能不能转化为求最长上升子序列呢？

可以！

证明过程

以下解释选自 $洛谷题解$（略有修改）

关于为什么可以转化成 LIS（即为最长上升子序列） 问题，这里提供一个解释。

A序列:3 2 1 4 5
B序列:1 2 3 4 5

我们不妨给它们重新标个号：把 $3$ 标成 a ,把 $2$ 标成 b ，把 $1$ 标成c$???????$

于是这两个序列变成：

A序列: a b c d e
B序列: c b a d e

这样标号之后，LCS（即为最长公共子序列）长度显然不会改变。但是出现了一个性质：

两个序列的子序列，一定是 A 的子序列。而 A 本身就是单调递增的。

因此这个子序列是单调递增的。

换句话说：

只要这个子序列在 B 中单调递增，它一定是 A 的子序列。

举个例子：在 B 中 a d e 是单调递增的（这个应该显而易见吧），对应回原数组位 3 4 5，我们看一下 A 中的 3 4 5 确实是公共子序列。

那么在 B 的上升子序列中哪一个最长呢？

当然是 B 的 LIS 最长（毕竟是最长上升子序列）。

自此完成转化。

AC实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,len=1;
int num_1[N],num_2[N],dui_1[N],d[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&num_1[i]);
		dui_1[num_1[i]]=i;
		num_1[i]=i;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&num_2[i]);
		num_2[i]=dui_1[num_2[i]];
	}
	d[1]=num_2[1];
   	//完成转化
    for(int i=2;i<=n;i++){
        if(num_2[i]==d[len])continue;
        if(num_2[i]>d[len])d[++len]=num_2[i];
        else *lower_bound(d+1,d+len+1,num_2[i])=num_2[i];//关键的二分啊！
    }
    printf("%d",len);
    return 0;
}

最近又看了看题解，发现还有使用树状数组和线段树写的，大家可以尝试一下。
大家点个赞吧！