动态规划—LCS最长公共子序列

Main.java

package com.company.zzh;

public class Main {

    public static void main(String[] args) {
        System.out.println("非连续最长子序列" + findLCS("AB1C2", "aAB34CD", false));
        System.out.println("连续最长子序列" + findLCS("AB1C2", "aAB34CD", true));
    }

    public static int findLCS(String A, String B, boolean close) {//clsoe要求子序列必须连续
        int aL = A.length(), bL = B.length();
        //创建dp数组
        int[][] dp = new int[aL][bL];
        char[] a = A.toCharArray(), b = B.toCharArray();
        int i, j, closeMax = 0;
        for (i = 0; i < aL; i++) {
            for (j = 0; j < bL; j++) {
                if (a[i] == b[j]) {
                    //1如果不在边缘，当前值=左上角的值+1；如果在边缘，当前值就是1
                    dp[i][j] = i == 0 || j == 0 ? 1 : dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > closeMax) {//要求子序列必须连续
                        closeMax = dp[i][j];
                    }
                } else {
                    //如果不要求子序列连续，那么当前值需要取 左边 和 上边 的较大者
                    if (!close) {
                        dp[i][j] = Math.max(dp[Math.max(i - 1, 0)][j], dp[i][Math.max(j - 1, 0)]);
                    }
                    //如果要求子序列连续，那么当前值就是数组初始化时候的默认的0，不需要再做处理了
                }
            }
        }

        Util.printAray(dp, A, B);//打印二维数组
        return close ? closeMax : dp[aL - 1][bL - 1];
    }
}

Util.java，这个是工具类，用来打印二维数组，看起来直观一些：

package com.company.zzh;

public class Util {
    public static <T> void printAray(int[][] arr, String A, String B) {
        System.out.print("   ");
        for (int i = 0; i < B.length(); i++) {
            boolean end = i == B.length() - 1;
            System.out.print(B.charAt(i) + (end ? "" : ", "));
        }
        System.out.println();
        int row = arr.length;
        int col = arr[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (j == 0) {
                    System.out.print(A.charAt(i) + "  ");
                }
                boolean end = j == col - 1;
                System.out.print(arr[i][j] + (end ? "" : ", "));
            }
            System.out.println();
        }
    }
}

解释下Main.java代码中的clsoe变量，一般这个值是false表示子序列可以是非连续的。如果为true表示要求子序列必须是连续的，这样的需求其实比为false更好做。

输出的结果：

   a, A, B, 3, 4, C, D
A  0, 1, 1, 1, 1, 1, 1
B  0, 1, 2, 2, 2, 2, 2
1  0, 1, 2, 2, 2, 2, 2
C  0, 1, 2, 2, 2, 3, 3
2  0, 1, 2, 2, 2, 3, 3
非连续最长子序列3
   a, A, B, 3, 4, C, D
A  0, 1, 0, 0, 0, 0, 0
B  0, 0, 2, 0, 0, 0, 0
1  0, 0, 0, 0, 0, 0, 0
C  0, 0, 0, 0, 0, 1, 0
2  0, 0, 0, 0, 0, 0, 0
连续最长子序列2