最长子字符串有关问题-动态规划法

最长子字符串问题-动态规划法
public class LCSProblem  
{ 
    public static void main(String[] args) 
    { 
        String[] x = {"","A", "B", "C", "B", "D", "A", "B"}; 
        String[] y = {"","B", "D", "C", "A", "B", "A"};
         
        char[][] b = getLCSLength(x, y); 
         
        display(b, x, x.length -1, y.length - 1); 
    }  //B C B A
     
    public static char[][] getLCSLength(String[] x, String[] y) 
    { 
        char[][] b = new char[x.length][y.length]; 
        int[][] c = new int[x.length][y.length]; 
         
        for(int i=1; i< x.length; i++) 
        { 
            for(int j=1; j< y.length; j++) 
            { 
                if(x[i] == y[j]) 
                { 
                    c[i][j] = c[i-1][j-1] + 1; 
                    b[i][j] = '↖'; 
                } 
                else if(c[i-1][j] >= c[i][j-1]) 
                { 
                    c[i][j] = c[i-1][j]; 
                    b[i][j] = '↑'; 
                } 
                else 
                { 
                    c[i][j] = c[i][j-1]; 
                    b[i][j] = '←'; 
                } 
            } 
        }  

   for(int i=0; i < x.length; i++){
  for(int j=0; j < y.length; j++)
   System.out.print(c[i][j]+" ");
  System.out.println();
}

         
        return b; 
    } 
     
    public static void display(char[][] b, String[] x, int i, int j) 
    { 
        if(i == 0 || j == 0) 
            return; 
         
        if(b[i][j] == '↖') 
        { 
            display(b, x, i-1, j-1); 
            System.out.print(x[i] + " "); 
        } 
        else if(b[i][j] == '↑') 
        { 
            display(b, x, i-1, j); 
        } 
        else 
        { 
            display(b, x, i, j-1); 
        } 
    } 
}