最长公共子序列
作者:
husheng
,
2022-05-11 12:45:13
,
所有人可见
,
阅读 157
import java.util.Scanner;
public class 最长公共子序列 {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] a=new int[n+5];
int[] b=new int[n+5];
for(int i=1;i<=n;i++) {
a[i]=input.nextInt();
}
for(int j=1;j<=n;j++) {
b[j]=input.nextInt();
}
//对于a串中前i个字符,b串中前j个字符所能取得的最长公共子序列的长度
int[][] dp=new int[n+5][n+5];
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
dp[i][j]=dp[i-1][j];
if(a[i]==b[j]) {
dp[i][j]=Math.max(dp[i][j], dp[i-1][j-1]+1);
}else {
dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
System.out.println(dp[n][n]);
}
}