观看了麻省理工大学的算法导论课程，讲解了动态规划求解最长公共子序列的方法，受益匪浅，现做个总结。
1、公共子序列和公共子串的区别
公共子串是指连续的公有字符串，公共子序列是指两个字符串都任意删除0个或多个字符后得到的公有字符串，子序列可以是不连续的。
举个例子吧，有两个字符串，串A为“1 2 3 4 5 6 7”，串B 为“1 3 4 5 8 7”，很明显，A和B的公共子串为“3 4 5”，A和B的公共子序列可以是 “3 5”，或是“1 3 7”，等等。
最长公共子串：在两个字符串中找到一个最长的公共子串，要求子串在原串中是连续的。
最长公共子序列：在两个字符串中找到一个最长的公共子串，不要求子串在原串中是连续的。
2、问题描述
现有两个序列x[1...m],y[1...n]，要求出两个序列的最长公共子序列。
假设x和y如下：
x[1...m] = {A, B, C, B, D, A, B};
y[1...n] = {B, D, C, A, B, A}；
3、穷举法
- 求出x中所有包含的子序列数：2^m
- 检测y中是否包含每一个子序列：n
时间复杂度为：O(2^m * n)，消耗天价的时间，明显不合格。
4、动态规划求解
先假设有 C[i,j] = | LCS(x[1...i] , y(1...j)) |，则有：
根据上面要求可以写出求解LCS问题的伪代码：
1 LCS(x,y,i,j) 2 if x[i] = y[j] 3 then C[i,j] ← LCS(x,y,i-1,j-1)+1 4 else C[i,j] ← max{LCS(x,y,i-1,j),LCS(x,y,i,j-1)} 5 return C[i,j]
为了在求解过程中不进行重复计算，用一个二维数组来暂时存储已经计算过的值，牺牲空间来获得时间上的优化。
代码如下：
1 public class LCS { 2 public static int[][] vals ; 3 4 public static int getLCS(String str1,String str2){ 5 int len1 = str1.length(); 6 int len2 = str2.length(); 7 8 vals = new int[len1+1][len2+1]; 9 10 for(int i=0;i<len1;i++){ 11 // 二维数组从[1][1]开始进行有效存储 12 int fi = i+1; 13 for(int j=0;j<len2;j++){ 14 int fj = j+1; 15 //字符相同 16 if(str1.charAt(i) == str2.charAt(j)){ 17 // 满足第一种状况 18 vals[fi][fj] = vals[fi-1][fj-1] + 1; 19 //字符不相同 20 }else if(str1.charAt(i) != str2.charAt(j)){ 21 //满足第二种状况 22 vals[fi][fj] = Math.max(vals[fi-1][fj],vals[fi][fj-1]); 23 } 24 } 25 } 26 27 for(int i=0;i<len1;i++){ 28 System.out.println(Arrays.toString(vals[i])); 29 } 30 31 return vals[len1][len2]; 32 } 34 public static void main(String[] args) { 36 String str1 = "ABCBDAB"; 37 String str2 = "BDCABA"; 38 System.out.println(getLCS(str1,str2)); 41 } 42 }
输出结果：
[0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 1, 1, 1] [0, 1, 1, 1, 1, 2, 2] [0, 1, 1, 2, 2, 2, 2] [0, 1, 1, 2, 2, 3, 3] [0, 1, 2, 2, 2, 3, 3] [0, 1, 2, 2, 3, 3, 4] 4