动态规划+回溯法查找：两字符串的最长公共子序列LCS

测试

bdcaba

abcbdab

最长公共子序列长度：4

状态转移矩阵如下：

* * * * * * * *

* ^ \ < \ < < \

* ^ ^ ^ ^ \ < <

* ^ ^ \ < ^ ^ ^

* \ ^ ^ ^ ^ \ <

* ^ \ ^ \ < ^ \

* \ ^ ^ ^ ^ \ ^

最长公共子序列：b a d b

--------

abcbdab

bdcaba

最长公共子序列长度：4

状态转移矩阵如下：

* * * * * * *

* ^ ^ ^ \ < \

* \ < < ^ \ <

* ^ ^ \ < ^ ^

* \ ^ ^ ^ \ <

* ^ \ ^ ^ ^ ^

* ^ ^ ^ \ ^ \

* \ ^ ^ ^ \ ^

最长公共子序列：a b c b

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

enum SrcDir {
    SRC(-1, "源头格网", "*"),
    UP(0, "数据源自上方格网", "^"),
    LEFT(1, "数据源自左边格网", "<"),
    LEFTUP(2, "数据源自左上方格网", "\\");
    public int code;
    public String msg;
    public String dir;
    SrcDir(int code, String msg, String dir) {
        this.code = code;
        this.msg = msg;
        this.dir = dir;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];//动态规划矩阵
        SrcDir[][] status = new SrcDir[len1 + 1][len2 + 1];//状态转移矩阵
        for (int i = 0; i <= len1; i++) {
            for (int j = 0; j <= len2; j++) {
                //初始化
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                    status[i][j] = SrcDir.SRC;
                } else {
                    //状态转移
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                        status[i][j] = SrcDir.LEFTUP;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                        status[i][j] = dp[i - 1][j] >= dp[i][j - 1] ? SrcDir.UP : SrcDir.LEFT;
                    }
                }
            }
        }
        //从右下角回溯到0行或者0列结束
        int i = len1, j = len2;
        List<Character> lcs = new ArrayList<>();
        while (i > 0 && j > 0) {
            if (status[i][j].code == 0) {
                i--;
            }
            if (status[i][j].code == 1) {
                j--;
            }
            if (status[i][j].code == 2) {
                //回溯路径上的状态为LEFTUP(2, "数据源自左上方格网", "\\")的即为公共字符
                lcs.add(str1.charAt(i - 1));
                i--;
                j--;
            }
        }
        System.out.println("最长公共子序列长度：" + dp[len1][len2]);
        System.out.println("状态转移矩阵如下：");
        for (SrcDir[] val : status) {
            for (SrcDir val1 : val) {
                System.out.print(val1.dir + " ");
            }
            System.out.println();
        }
        System.out.print("最长公共子序列：");
        for (char val : lcs) {
            System.out.print(val + " ");
        }
    }
}