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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer st = new StreamTokenizer(br);
    st.nextToken();
    int len1 = (int) st.nval;
    st.nextToken();
    int len2 = (int) st.nval;
    st.nextToken();
    String s1 = st.sval;
    st.nextToken();
    String s2 = st.sval;
    int[][] dp = new int[len1 + 1][len2 + 1];//不用dp[len1][len2]是为了统一第一个字符的判断
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    System.out.println(dp[len1][len2]);
}
}