最长公共子序列

Java练习题（2022年秋季学期–软件工程）

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式:
第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

1≤N,M≤1000

输出格式:
输出一个整数，表示最大长度，结尾无空格换行。

输入样例:
在这里给出一组输入。例如：

4 5
acbd
abedc

输出样例:
在这里给出相应的输出。例如：

3

import java.util.*;

public class  Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        String a=input.next();
        String b=input.next();
        int x=findLCS(a,n,b,m);
        System.out.print(x);
    }
    public static int findLCS(String A, int n, String B, int m) {
        int[][] dp = new int[n+1][m+1];
        for(int i  = 0;i<=n;i++){
            dp[i][0] = 0;
        }
        for(int i  = 0;i<=m;i++){
            dp[0][i] = 0;
        }
        char[] str1 = A.toCharArray();
        char[] str2 = B.toCharArray();
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if(str1[i-1]==str2[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]);
                }
            }
        }
        return dp[n][m];
    }
}