我们先来了解一下相关概念： （1）子序列： 一个序列A ＝ a1,a2,……an,中任意删除若干项，剩余的序列叫做A的一个子序列。也可以认为是从序列A按原顺序保留任意若干项得到的序列。
例如： 对序列 1,3,5,4,2,6,8,7来说，序列3,4,8,7 是它的一个子序列。 对于一个长度为n的序列，它一共有2^n 个子序列，有(2^n – 1)个非空子序列。
请注意：子序列不是子集，它和原始序列的元素顺序是相关的。
（2）公共子序列 ： 顾名思义，如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。
例如：
对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说
序列1,8,7是它们的一个公共子序列。
请注意： 空序列是任何两个序列的公共子序列。 例如： 序列1,2,3和序列4,5,6的公共子序列只有空序列。
（3）最长公共子序列
A和B的公共子序列中长度最长的（包含元素最多的）叫做A和B的公共子序列。 仍然用序列1,3,5,4,2,6,8,7和序列1,4,8,6,7,5
它们的最长公共子序列是：
1,4,8,7 1,4,6,7
最长公共子序列的长度是4 。 请注意: 最长公共子序列不唯一。
请大家用集合的观点来理解这些概念，子序列、公共子序列以及最长公共子序列都不唯一，所以我们通常说一个最长公共子序列，但显然最长公共子序列的长度是一定的。
最长公共子序列问题就是求序列A= a1,a2,……an, 和B = b1,b2,……bm,的一个最长公共子序列。
用公式可表示为： 因为最长公共子序列不唯一，让我们把问题简化，如何求出两个序列的最长公共子序列长度呢？
首先能我们想到的恐怕是暴力枚举？那我们先来看看：序列A有 2^n 个子序列，序列B有 2^m 个子序列，如果任意两个子序列一一比较，比较的子序列高达 2^(n+m) 对，这还没有算具体比较的复杂度。
或许你说，只有长度相同的子序列才会真正进行比较。那么忽略空序列，我们来看看：对于A长度为1的子序列有C(n,1)个，长度为2的子序列有C(n,2)个，……长度为n的子序列有C(n,n)个。对于B也可以做类似分析，即使只对序列A和序列B长度相同的子序列做比较，那么总的比较次数高达： C(n,1)*C(m,1)*1 + C(n,2) * C(m,2) * 2+ …+C(n,p) * C(m,p)*p 其中p = min(m, n)。
如此，简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。 为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。
我们先来看看递归法：
public class 递归法实现最大公共子序列 { public static int lcs(char[] x, char[] y, int i, int j) { if (i == 0 || j == 0) { // 当这里（i==0位置的元素）x串为空的时候，没有公共串。 // 所以我们返回的公共子序列的长度为零。 // 当我们的这串为空（x==0）的时候， // 实际上我们传的的字符串的第0个元素为'A'， // 而不是空串，所以返回0是不对的。因为'A'在里头比的时候， // 可能有公共串，则我们要在两个字符串开头加0号字符。 return 0; } else if (x[i] == y[j]) { return lcs(x, y, i - 1, j - 1) + 1; } return max(lcs(x, y, i - 1, j), lcs(x, y, i, j - 1)); // 返回x串的第i个元素的第j个串和y串的第i的子串到j-1的串的最大值。 } private static int max(int a, int b) { if (a > b) { return a; } return b; } public static void main(String[] args) { String s1 = "ABCBDAB"; // 创建两个字符数组 char[] c1 = new char[s1.length() + 1]; // 字符串s1的长度加个1 char[] t1 = s1.toCharArray(); // 字符串可以通过此方法转成字符串数组 c1[0] = (char) 0; // 让c1[0]保存0号字符 // 遍历s1字符串里的每一个字符 for (int i = 0; i < t1.length; i++) { c1[i + 1] = t1[i]; // 将数组t1[i]的字符赋到c1[i+1]中 } // 同上 String s2 = "BDCABA"; char[] c2 = new char[s1.length() + 1]; char[] t2 = s2.toCharArray(); // 字符串可以通过此方法转成字符串数组 c2[0] = (char) 0; for (int i = 0; i < t2.length; i++) { c2[i + 1] = t2[i]; } System.out.println(lcs(c1, c2, c1.length - 1, c2.length - 1)); } }但是，使用递归法，时间复杂度较大。而由此我们想到了大多新手较为熟悉的备忘录法。
public class 备忘录法查找最大公共子序列 { public static int lcs(char[] x, char[] y, int i, int j, int[][] bak // *在该括号里初始化bak，则每次初始化成一样的值。 // * 且每次初始化，原来的值就被覆盖掉了。 // * 而备忘录是对递归的每一层进行记录。 ) { // 那么每一次我没在算第i行j列字符之前的子串时， // 我们都可以先判断一下。 // 而这个公共子串的长度已经被算出来了。 // 我们在这里只需要判断一下，bak[i][j]!=-1。 // 如果不是-1，就说明不是初始化的值，就说明有值了。 // 这时候，我们就把它返回出去就行了。 // if (bak[i][j] != -1) { return bak[i][j]; } if (i == 0 || j == 0) { bak[i][j] = 0;// 这里需要注意的是，将0赋给bak[i][j]时，并没有返回。 // 当i==0，j==0的时候，同理将该值存到备忘录里。 } else if (x[i] == y[j]) { bak[i][j] = lcs(x, y, i - 1, j - 1, bak) + 1; } else bak[i][j] = max(lcs(x, y, i - 1, j, bak), lcs(x, y, i, j - 1, bak)); // 承接上面没有return，这里就需要加else， // 不然该处被执行，bak[i][j]所存的值就会被多减一次。 return bak[i][j]; // 从备忘录里返回。 } private static int max(int a, int b) { if (a > b) { return a; } return b; } public static void main(String[] args) { String s1 = "ABCBDAB"; char[] c1 = new char[s1.length() + 1]; char[] t1 = s1.toCharArray(); // 字符串可以通过此方法转成字符串数组 c1[0] = (char) 0; for (int i = 0; i < t1.length; i++) { c1[i + 1] = t1[i]; } String s2 = "BDCABA"; char[] c2 = new char[s2.length() + 1]; char[] t2 = s2.toCharArray(); // 字符串可以通过此方法转成字符串数组 c2[0] = (char) 0; for (int i = 0; i < t2.length; i++) { c2[i + 1] = t2[i]; } // 这里创建了一个备忘录数组 int[][] bak = new int[c1.length][c2.length]; // 而这里需要初始化一下bak，因为我们保存在保存字符串的时候， // 是有0号字符的值的，而不能默认是该值。 // 之所以要初始化bak，是因为这个数组里是保存有字符0这个值的。 // 当i和j都等于0的时候，公共子串就是0。而有这个0值的时候， // 就要将其存到备忘录里。那么给bak的默认值为0就不对了，这样容易造成混淆。 // 那么我们在这里遍历一下 for (int i = 0; i < c1.length; i++) { for (int j = 0; j < c2.length; j++) { bak[i][j] = -1; // 在这里我们给其初始化为-1，这是数组里没有的值的。 // 由此可作为判断，并给传进去。当然我们初始化bak的时候， // 只能在外边初始化，而不能在里头初始化。 } } System.out.println(lcs(c1, c2, c1.length - 1, c2.length - 1, bak)); } }虽然，备忘录法是时间富足度降低，但是这也是在增加空间复杂度的方法下进行的整改。至此，我们还可以想到动态规划中最为高效的方法——字底向上法。
public class 自底向上查找最大公共子序列 { public static int lcs(char[] x, char[] y, int i, int j, int[][] bak // 这里bak[][]已经不是备忘录了，而是从表中取值的。 // 而这里bak[][]也不用初始化了。 ) { for (int ii = 0; ii <= i; ii++) { for (int jj = 0; jj <= j; jj++) { // 这里i和j是索引，不是总长度。所以i和j不需要减一。 if (ii == 0 || jj == 0) { bak[ii][jj] = 0; } else if (x[ii] == y[jj]) { bak[ii][jj] = bak[ii - 1][jj - 1] + 1; // 这里就不用递归方法了， // 因为该元素之前的元素的值已经求出来了。 // 然后再在此基础上进行累加。 } else bak[ii][jj] = max(bak[ii - 1][jj], bak[ii][jj - 1]); } } return bak[i][j]; // 返回最大值 } private static int max(int a, int b) { if (a > b) { return a; } return b; } public static void main(String[] args) { String s1 = "ABCBDAB"; char[] c1 = new char[s1.length() + 1]; char[] t1 = s1.toCharArray(); // 字符串可以通过此方法转成字符串数组 c1[0] = (char) 0; for (int i = 0; i < t1.length; i++) { c1[i + 1] = t1[i]; } String s2 = "BDCABA"; char[] c2 = new char[s2.length() + 1]; char[] t2 = s2.toCharArray(); // 字符串可以通过此方法转成字符串数组 c2[0] = (char) 0; for (int i = 0; i < t2.length; i++) { c2[i + 1] = t2[i]; } // 这里创建了一个备忘录数组 int[][] bak = new int[c1.length][c2.length]; // 而这里需要初始化一下bak，因为我们保存在保存字符串的时候， // 是有0号字符的值的，而不能默认是该值。 // 之所以要初始化bak，是因为这个数组里是保存有字符0这个值的。 // 当i和j都等于0的时候，公共子串就是0。而有这个0值的时候， // 就要将其存到备忘录里。那么给bak的默认值为0就不对了，这样容易造成混淆。 // 那么我们在这里遍历一下 for (int i = 0; i < c1.length; i++) { for (int j = 0; j < c2.length; j++) { bak[i][j] = -1; // 在这里我们给其初始化为-1，这是数组里没有的值的。 // 由此可作为判断，并给传进去。当然我们初始化bak的时候， // 只能在外边初始化，而不能在里头初始化。 } } System.out.println(lcs(c1, c2, c1.length - 1, c2.length - 1, bak)); } }注意： 这里使用了循环计算表格里的元素值，而不是递归，如果使用递归需要已经记录计算过的元素，防止子问题被重复计算。
