记住一句话:只要你能说得通的代码你都可以去试一遍,
因为本身代码就是不存在的,我们要做得就是创作一个功能。所以只要你能用一个正当的理由说通这个代码,那个这个代码就可以实现你说的理由,如果不能AC,那一定是有某个状态你没想到。
Dp问题本身就是思想,我们从源头出发,用数学公式证明、用现实例子证明、用过程证明、、、
/*
状态转移方程——>f[i][j]=Max(f[i-1][j-1],f[i-1][j],f[i][j-1],f[i-1][j-1]+1)
1,f[i-1][j]或f[i][j-1]包含f[i-1][j-1]
2,f[i-1][j]可以包含了j存在的状态且被包含在f[i][j]中,所以f[i-1][j]可以用也可以替代存在j的状态。
3,i存在j存在的状态表示:因为集合是一个公共子序列集合,所以存在i j一定是代表两个序列相等,且最后一项
是i与j,因为f[i-1][j-1]代表a里前i-1和数和b里j-1个数相等,然后末端插入i j,且相等,那么这个
子序列长度会加1——>i==j
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int f[][]=new int[1010][1010];
String a=sc.next();
String b=sc.next();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
if(a.charAt(i-1)==b.charAt(j-1)){
//a[i]!=b[j]时,i和j就不存在相同子序列中
//因为i是最后一项,j也是最后一项,最后一项不相等集合就不存在i和j
f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
}
}
}
System.out.println(f[n][m]);
}
}