最長連続共通サブシーケンス---動的計画


2つの文字列について、最も長い共通サブシーケンスの長さを求める効率的なアルゴリズムを設計し、文字が連続して与えられた文字列AとBを必要とせず、最も長い共通サブシーケンスの長さを返します.2つの列の長さが300以下であることを保証します.試験例:1 A 2 C 3 D 4 B 56 B 1 D 23 CA 45 B 6 A戻り:6
public class   {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String A=sc.next();
        String B=sc.next();
        sc.close();
        int n=A.length();
        int m=B.length();
        char a[]=A.toCharArray();
        char b[]=B.toCharArray();
        int[][] dp=new int[n + 1][m + 1];
        // A  i  B  j   
        for (int i=1;i<=n;i++) {
            for (int j=1;j<= m;j++){
                if (a[i-1]==b[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[n][m]);
    }
}