思路

给定两个数组 x[] y[]，表示两个序列

构建一个 [x.length] [y.length] 的二维数组 m，用于记录动态规划表

构建一个嵌套循环

• i 表示 x 的下标，[1, x.length]
  • j 表示 y 的下标，[1. y.length]
    • 如果 x[i] == y[i]，表明出现一个新的子序列，m[i] [j] = m[i - 1] [j - 1]
    • 若 x[i] != y[i]，则需要从 m[i - 1] [j] 和 m[i] [j - 1] 中取一个最大值

遍历完成后取最右下角的值既为最优子序列个数

代码

void LCS(char[] X, char[] Y) {
        int xLen = X.length;
        int yLen = Y.length;
        int[][] c = new int[xLen + 1][yLen + 1];

        for (int i = 0; i < yLen + 1; ++i) {
            c[0][i] = 0;
        }
        for (int i = 0; i < xLen + 1; ++i) {
            c[i][0] = 0;
        }

        for (int i = 1; i < xLen + 1; ++i) {
            for (int j = 1; j < yLen + 1; ++j) {
                if (X[i - 1] == Y[j - 1]) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                } else c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
            }
        }

        for (int i = 1; i < xLen + 1; ++i) {
            for (int j = 1; j < yLen + 1; ++j) {
                System.out.print(c[i][j] + "\t");
            }
            System.out.println();
        }
    }