LCS 最长公共子序列

子序列和子串的区别：

子序列不要求连续，子串必须连续。

动态规划过程

定义f(i,j):表示集合：A串从0-i和B串从0-j最长公共子序列
属性：max（最大值）

时间复杂度

总共n^2个状态，每个状态的转移是常数级别的。所以时间复杂度是o(n^2)

/**LCS 最长公共子序列
 * 子序列和子串的区别：子序列不要求连续，子串必须连续。
 * 定义f(i,j):表示集合：A串从0-i和B串从0-j最长公共子序列
 *                属性：max（最大值）
 * 划分集合：1.i,j位置字符都在LCS上（这个情况可能不存在）f(i-1,j-1)+1;
 *           2.i在LCS上，j不在。这个状态不好单独拿出来，但是可以用一个比他大的集合代替他，因为是求max，所以扩大集合不影响
 * 最后结果。所以可以用i位置的字符在不在LCS都行，但是j位置上的字符不在LCS上:f(i,j-1);
 *           3.j在LCS上，i不在。同上，这个集合可以用f(i-1,j)来代替。
 *           4.i,j位置的字符都不在LCS上，也就是f(i-1,j-1)  这个一定小于第一种情况，所以直接不看了。
 *           综上一共三种集合，有一种是不一定存在的得到如下递推式子：
 *           f(i,j)=max(f(i-1,j),f(i,j-1),if(i,j位置字符相等)?:f(i-1,j-1)+1:不参与比较);
*/
import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt()+1;
        int M=sc.nextInt()+1;
        String a=" "+sc.next();//字符串问题一般都要在前面加个空格，方便计算的。
        String b=" "+sc.next();
        int[][] f=new int[N][M];
        //初始化：只要i，j任何一个是0 那么f[i][j]=0，因为数组自己初始化就是0，所以就没有人为进行初始化。
        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)==b.charAt(j)) f[i][j]=Math.max(f[i][j],f[i-1][j-1]+1);
            }
        }
        System.out.println(f[N-1][M-1]);
    }
}