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

给定两个序列X，Y，求X和Y的最长公共子序列
i = 0 || j =0 ----->c[i,j] = 0;
i>0,j>0 x=y时， c[i][j] = c[i-1][j-1] + 1
i,j > 0 ,x!=y, c[i][j] = max{c[i-1][j],c[i][j-1]}

    public static int[][] subArr(String[] x, String[] y) {

        int[][] arr = new int[x.length][y.length];

        //保存
        int[][] subArr = new int[x.length][y.length];

        // 1, -1, 0只是在回溯的时候标识，数据的来源，从哪来，回溯的时候从哪回
        for (int i = 1; i < x.length; i++) {

            for (int j = 1; j < y.length; j++) {

                //数据相等时，则在上一位基础上加一
                if (x[i].equals(y[j])) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                    subArr[i][j] = 1;
                    continue;
                }
                //判断当时最长公共子序列最大值，是从哪个位置获取
                if (arr[i - 1][j] >= arr[i][j - 1]) {
                    arr[i][j] = arr[i - 1][j];
                    subArr[i][j] = 0;
                } else {
                    arr[i][j] = arr[i][j - 1];
                    subArr[i][j] = -1;
                }
            }

        }

        return subArr;
    }

    public static void display(int[][] subArr, String[] x, int i, int j) {
        if (i == 0 || j == 0) {
            return;
        }

        if (subArr[i][j] == 1) {

            display(subArr, x, i - 1, j - 1);
            System.out.printf("  " + x[i]);

        } else if (subArr[i][j] == 0) {

            display(subArr, x, i - 1, j);

        } else if (subArr[i][j] == -1) {

            display(subArr, x, i, j - 1);

        }

    }