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

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        input.nextLine();
        String s1;
        s1 = input.nextLine();
        String s2 = input.nextLine();
        
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for(int i = 1; i <= s1.length(); i++){
            for(int j = 1; j <= s2.length(); j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    //如果有s2中有s1对应的字符
                    //那么这个字符可以作为最长公共子序列的终点
                    //dp[i][j]的含义就是s1从0到i，s2从0到j时的最长公共子序列的长度
                    //与前文的对应关系为dp[i][j] = dp[i-1][j-1]+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[s1.length()][s2.length()]);
    }
}