AcWing 897. 最长公共子序列
原题链接
简单
作者:
hhu-菜菜
,
2021-05-19 20:12:44
,
所有人可见
,
阅读 213
import java.util.Scanner;
class Main{
static final int N = 1010;
static int n,m;
static char[] a = new char[N];
static char[] b = new char[N];
static int[][] dp = new int[N][N];
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
m = reader.nextInt();
String s1 = reader.next();
String s2 = reader.next();
for(int i = 1;i <= n;i++){
a[i] = s1.charAt(i-1);
}
for(int i = 1;i <= m;i++){
b[i] = s2.charAt(i-1);
}
reader.close();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);//每次跟新01,10的情况
//如果相等,就取他们的最大值
if(a[i] == b[j]) dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
}
}
System.out.println(dp[n][m]);
}
}