一、问题描述

给定两个序列 X={x1,x2,x3,x4,x5,x6......xm} Y={y1,y2,y3,y4,y5,y6.........yn} 找到X和Y的一个最长公共子序列。
示例如下

最长公共子序列.png

二、解题思路

首先想到的就是暴力法，找到X的所有的子序列，然后找到Y的所有的子序列，然后进行对比，X的子序列有2^m个，所以算法的复杂度就变成了指数阶。
其次分析问题，看看问题是否满足最优子结构，我们假设Z = {z1,z2,z3,z4......zk } 是 X={x1,x2,x3,x4,x5,x6......xm} Y={y1,y2,y3,y4,y5,y6.........yn} 的最长公共子序列，那么当xm = yn = zk 的时候，Z = {z1,z2,z3,z4......zk-1 } 是 X={x1,x2,x3,x4,x5,x6......xm-1} Y={y1,y2,y3,y4,y5,y6.........yn-1} 的最长公共子序列。
依次类推，我们可以发现最优解符合状态转移方程。

状态转移方程.png

可以发现，最优解是从一个元素慢慢向上递推的，所以我们可以建立dp表来进行演算。

三、思考

这玩意如何建立dp表？可以使用两个二维数组，一个是dp表，一个是记录数据来源的表，记录关系可以如下

dp表设计.png

相应的dp表如下

dp表.png

源表

源表.png

四、实现

public class LongestPublicStr {
    public static void main(String[] args) {
        char[] str1 = new char[]{'a', 'b', 'c', 'a', 'd', 'a', 'b'};
        char[] str2 = new char[]{'b', 'a', 'c', 'd', 'b', 'a'};
        System.out.println(dynamicLongestPublicStr(str1, str2));

    }

    /**
     * x,y     1
     * x-1,y   2
     * x,y-1   3
     *
     * @param str1
     * @param str2
     * @return
     */
    public static char[] dynamicLongestPublicStr(char[] str1, char[] str2) {
        //初始化dp数组
        int[][] dpSource = new int[str1.length + 1][str2.length + 1];
        int[][] dpValue = new int[str1.length + 1][str2.length + 1];

        for (int i = 0; i <= str1.length; i++) {
            dpSource[i][0] = 0;
            dpValue[i][0] = 0;
        }
        for (int i = 0; i <= str2.length; i++) {
            dpSource[0][i] = 0;
            dpValue[0][i] = 0;
        }

        //循环数组str1
        for (int i = 0; i < str1.length; i++) {
            //循环数组str2
            int x = i + 1;
            for (int j = 0; j < str2.length; j++) {
                int y = j + 1;

                //判断是否相等
                if (str1[i] == str2[j]) {
                    dpSource[x][y] = 1;
                    dpValue[x][y] = dpValue[x - 1][y - 1] + 1;

                } else {
                    if (dpValue[x - 1][y] > dpValue[x][y - 1]) {
                        dpSource[x][y] = 2;
                        dpValue[x][y] = dpValue[x - 1][y];
                    } else {
                        dpSource[x][y] = 3;
                        dpValue[x][y] = dpValue[x][y - 1];
                    }
                }
            }
        }

        //输出最长公共子序列
        //循环数组str1
        int x = str1.length;
        int y = str2.length;

        char[] s = new char[dpValue[x][y]];
        int index = dpValue[x][y];

        while (x > 0 && y > 0) {
            //x=y情况
            if (dpSource[x][y] == 1) {
                s[index - 1] = str1[x - 1];
                x -= 1;
                y -= 1;
                index--;
                continue;
            }

            //x-1,y   2
            if (dpSource[x][y] == 2) {
                x -= 1;
                continue;
            }

            //x,y-1   3
            if (dpSource[x][y] == 3) {
                y -= 1;
                continue;
            }
        }
        return s;
    }
}