动态规划-最长公共子序列

import java.util.*;
import java.io.*;
public class LCSsequence {
    public static void main(String arg[]){
        char[] x=new char[100];
        char[] y=new char[100];
        int i,m,n;
        int[][] c=new int[100][100];
        int[][] s=new int[100][100];
        Scanner input=new Scanner(System.in);
        String str1=input.nextLine();
        String str2=input.nextLine();
        for(i=0;i<str1.length();i++){
            x[i+1]=str1.charAt(i);
        }
        for(i=0;i<str2.length();i++){
            y[i+1]=str2.charAt(i);
        }
        m=str1.length();
        n=str2.length();
        LCSLength(x,y,m,n,c,s);
        LCS(m,n,x,s);
    }
    static void LCSLength(char x[] ,char y[],int m,int n, int c[][], int b[][]){
        int i,j;
        for(i=1;i<=m;i++) c[i][0]=0;
        for(i=1;i<=n;i++) c[0][i]=0;
        for(i=1;i<=m;i++)
            for(j=1;j<=n;j++){
                if(x[i]==y[j]){
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }
                else if(c[i-1][j]>=c[i][j-1]){
                    c[i][j]=c[i-1][j];
                    b[i][j]=2;
                }
                else{
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
    }
    static void LCS(int i ,int j, char x[] ,int b[][])
    {
         if (i ==0 || j==0) return;
         if (b[i][j]== 1)
         {
             LCS(i-1,j-1,x,b);
              System.out.print(x[i]);
         }
         else if (b[i][j]== 2)
              LCS(i-1,j,x,b);
          else LCS(i,j-1,x,b);
    }
}