最长公共子序列问题

问题分析

• 给定两个序列 X = { x₁, x₂, …, x_m }和 Y = { y₁, y₂, …, y_n }，找出 X 和 Y 的最长公共子序列。

算法分析

• 设序列 X = { x₁, x₂, …, x_m }和 Y = { y₁, y₂, …, y_n }的最长公共子序列为 Z = { z₁, z₂, …, z_k }，则。
  • 若 x_m = y_n，则 z_k = x_m = y_n，且 Z_k-1是 X_m-1和 Y_n-1的最长公共子序列。
  • 若 x_m != y_n，且 z_k != x_m，则 Z 是 X_m-1和 Y 的最长公共子序列。
  • 若 x_m != y_n，且 z_k != y_n，则 Z 是 X 和 Y_n-1的最长公共子序列。
• 其中 X_m-1 = { x₁, x₂, …, x_m-1 }, Y_n-1 = { y₁, y₂, …, y_n-1 }, Z = { z₁, z₂, …, z_k-1 }

代码实现

public class Solution {

    public static void main(String[] args) {
        int[] x = {30, 35, 12, 5, 11, 20, 25};
        int[] y = {30, 35, 15, 5, 10, 20, 25};
        int m = x.length;
        int n = y.length;
        int[][] c = new int[m + 1][n + 1];
        int[][] b = new int[m + 1][n + 1];
        Solution solution = new Solution();
        solution.LCSLength(x, y, c, b);
        System.out.println("最优值：");
        System.out.println("---------------c[i][j]-----------------");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.printf("%6d", c[i][j]);
            }
            System.out.println();
        }
        System.out.println("---------------b[i][j]-----------------");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.printf("%6d", b[i][j]);
            }
            System.out.println();
        }
        System.out.println("---------------最优解-----------------");
        solution.LCS(m, n, x, b);
    }

    public void LCSLength(int[] x, int[] y, int[][] c, int[][] b) {
        int m = x.length;
        int n = y.length;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (x[i - 1] == y[j - 1]) {
                    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;
                }
            }
        }
    }

    public void LCS(int i, int j, int[] 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 - 1] + " ");
        } else if (b[i][j] == 2) {
            LCS(i - 1, j, x, b);
        } else if (b[i][j] == 3) {
            LCS(i, j - 1, x, b);
        }
    }

}

• LCSLength(int[] x, int[] y, int[][] c, int[][] b) ：计算最长公共子序列最优值。
  • int x：序列 X
  • int y：序列 Y
  • int[][] c: c[i][j] 存储 X_i和 Y_j的最长公共子序列的长度。
  • int b[i][j]: b[i][j] 记录 c [i][j] 的值是由哪一个子问题的解得到的，其中 1 代表 左上, 2 代表 上, 3 代表 左
• LCS(m, n, x, b)：计算最长公共子序列最优解。
  • int m：序列 X 的长度。
  • int n：序列 Y 的长度。
  • int x：序列 X
  • int b[i][j]: b[i][j] 记录最优值是由哪一个子问题的解得到的，其中 1 代表 左上, 2 代表 上, 3 代表 左