# 最长公共子序列（LCS）

#### 递推版

```import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int[][] dp = new int[1000][1000];
String s1,s2;
s1 = cin.next();
s2 = cin.next();
int len1 = s1.length();
int len2 = s2.length();
for(int i = 0;i < len1;i++) {
for(int j = 0;j < len2;j++) {
if(s1.charAt(i) == s2.charAt(j))
dp[i + 1][j + 1] = dp[i][j] + 1;
else
dp[i + 1][j + 1] = Math.max(dp[i + 1][j],dp[i][j + 1]);
}
}
System.out.println(dp[len1][len2]);
}
}
}```

#### 递归版

```import java.util.Scanner;
public class Main {
public static int[][] res = new int[1000][1000];
public static String s1,s2;
public static int len1,len2;
public static int dp(int i,int j) {
if(i >= len1 || j >= len2)
return 0;
if(res[i][j] > 0)
return res[i][j];
if(s1.charAt(i) == s2.charAt(j))
return res[i + 1][j + 1] = dp(i + 1,j + 1) + 1;
int a = dp(i + 1,j);
int b = dp(i,j + 1);
return res[i + 1][j + 1] = Math.max(a,b);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
s1 = cin.next();
s2 = cin.next();
len1 = s1.length();
len2 = s2.length();
for(int i = 0;i < len1;i++)
for(int j = 0;j < len2;j++)
res[i][j] = 0;
System.out.println(dp(0,0));
}
}
}```

254 篇文章40 人订阅

0 条评论