【java】动态规划----查找最长公共子列

**例题：**给定两个序列，例如 X = “ABCBDAB”、Y = “BDCABA”，求它们的最长公共子序列的长度。

子序列：在给定的这两个母序列中，比如序列BCAB在母串ABCBDAB与BDCABA中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence,LCS），顾名思义，是指在所有的子序列中最长的那一个。在上述例子的中，最长公共子序列为BCAB。

求解算法
X串中有n个元素，Y串中有m个元素
1.暴力解法
假设 m<n， 对于母串Y，我们可以暴力找出2的m次方个子序列，然后依次在母串X中匹配，算法的时间复杂度会达到指数级O(n∗2的m次)。显然，暴力求解不太适用于此类问题。
2.递归方法
用递归的思路就是当数组X和Y对应位置字符相同时，直接求解下一个位置；当不同时取两种情况中的较大数值。
代码如下：

public class 最长公共子序列 {

	public static int lcs(char[] x, char[] y, int i, int j) {

		if (i == 0 || j == 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));

	}

	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];// 带0号字符的字符数组
		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]; //带0号的字符数组
		char[] t2 = s2.toCharArray();
		c1[0] = (char)0;
		for(int i = 0; i < t2.length; i++) {
			c2[i + 1] = t2[i];
		}
		
		System.err.println(lcs(c1, c2,c1.length - 1, c2.length - 1));

	}
}

用递归的方法优点是编程简单，容易理解。缺点是效率不高，有大量的重复执行递归调用，增加时间和空间复杂度。
　3.动态规划
　备忘录法
　动态规划采用二维数组来标识中间计算结果，避免重复的计算来提高效率。
　

public class 最长公共子序列 {

	public static int lcs(char[] x, char[] y, int i, int j, int[][] bak) {

		if (bak[i][j] != -1)  return bak[i][j];
			
		if (i == 0 || j == 0)  bak[i][j] = 0;
			
		if (i == 0 || j == 0)  return 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 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];// 带0号字符的字符数组
		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]; // 带0号的字符数组
		char[] t2 = s2.toCharArray();
		c1[0] = (char) 0;
		for (int i = 0; i < t2.length; i++) {
			c2[i + 1] = t2[i];
		}

		int[][] bak = new int[c1.length][c2.length];
		for (int i = 0; i < c1.length; i++) {
			for (int j = 0; j < c2.length; j++) {
				bak[i][j] = -1;
			}
		}

		System.err.println(lcs(c1, c2, c1.length - 1, c2.length - 1, bak));

	}
}