题解 | #最长公共子序列(一)#

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        final int N = in.nextInt();
        final int M = in.nextInt();
        String s1 = in.next();
        String s2 = in.next();

        int[][] maxLen = new int[N + 1][M + 1];
        //maxLen[i + 1][j + 1]表示以s1[i][j]子串的最长公共子序列长度
        for (int i = 0; i != N; ++i) {
            for (int j = 0; j != M; ++j) {
                int c1 = s1.charAt(i);
                int c2 = s2.charAt(j);
                if (c1 == c2) {
                    maxLen[i + 1][j + 1] = maxLen[i][j] + 1;
                } else {
                    maxLen[i + 1][j + 1] = Math.max(maxLen[i + 1][j], maxLen[i][j + 1]);
                }
            }
        }

        System.out.print(maxLen[N][M]);
    }
}