AcWing 897. 最长公共子序列
原题链接
简单
作者:
Zh1995
,
2019-09-22 15:48:14
,
所有人可见
,
阅读 982
算法思想
- 状态表示:
f[i][j]
代表S1中的前i
个字符,S2中的前j
个字符的最长公共子序列
- 状态转移:
- 如果
S1[i]==S2[j]
,那么最长公共子序列必然包含S1[i]/S2[j]
这个元素,可以先找到不包含S1[i]
和S2[j]
的最长公共子序列,再加上这个元素即可,不包含S1[i]
和S2[j]
的最长公共子序列就是f[i-1][j-1]
- 如果
S1[i]!=S2[j]
,最长的公共子序列中可能不包含S1[i](f[i-1][j])
,也可能不包含S2[j](f[i][j-1])
,也可能都不包含f[i-1][j-1]
代码
import java.util.*;
public class Main{
static int f[][]=new int[1010][1010];
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int len1=sc.nextInt();
int len2=sc.nextInt();
String s1=" "+sc.next();
String s2=" "+sc.next();
for(int i=1;i<=len1;i++)
for(int j=1;j<=len2;j++)
if(s1.charAt(i)==s2.charAt(j))
f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
else
f[i][j]=Math.max(f[i-1][j-1],Math.max(f[i-1][j],f[i][j-1]));
System.out.print(f[len1][len2]);
}
}