LCS 最长公共子序列

参考： http://www.cnblogs.com/liyukuneed/archive/2013/05/22/3090597.html

最长公共子序列是一个很经典的动态规划问题。

动态规划，众所周知，第一步就是找子问题，也就是把一个大的问题分解成子问题。这里我们设两个字符串A和B ，A = "a0, a1, a2, ..., am-1"，B = "b0, b1, b2, ..., bn-1"。

（1）如果am-1 == bn-1，则当前最长公共子序列为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列与am-1的和。长度为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列的长度+1。

（2）如果am-1 != bn-1，则最长公共子序列为max（"a0, a1, ..., am-2"与"b0, b1, ..., bn-1"的公共子序列，"a0, a1, ..., am-1"与"b0, b1, ..., bn-2"的公共子序列）

如果上述描述用数学公式表示，则引入一个二维数组c[][]，其中c[i][j]记录X[i]与Y[j]的LCS长度，再用一个二维数组b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，即，搜索方向。

这样我们可以总结出该问题的递归形式表达：

按照动态规划的思想，对问题的求解，其实就是对子问题自底向上的计算过程。这里，计算c[i][j]时，c[i-1][j-1]、c[i-1][j]、c[i][j-1]已经计算出来了，这样，我们可以根据X[i]与Y[j]的取值，按照上面的递推，求出c[i][j]，同时把路径记录在b[i][j]中（路径只有3中方向：左上、左、上，如下图）

代码

public static int lcsLen(String A, String B){
	int M = A.length(), N = B.length();
	int[][] lcsLen = new int[M+1][N+1];
	int[][] lcsDir = new int[M+1][N+1];
	for (int i = 0; i < M; i++)
		lcsLen[i][0] = 0;
	for (int i = 0; i < N; i++)
		lcsLen[0][i] = 0;
	
	for (int i = 1; i <= M; i++) 
		for (int j = 1; j <= N; j++) {
			if (A.charAt(i-1) == B.charAt(j-1)) {
				lcsLen[i][j] = 1 + lcsLen[i-1][j-1];
				lcsDir[i][j] = 0;  //左上
			}
				
			else {
				int x = lcsLen[i-1][j], y = lcsLen[i][j-1];
				if (x >= y) {
					lcsLen[i][j] = x;
					lcsDir[i][j] = 1;  // 上边
				}						
				else {
					lcsLen[i][j] = y;
					lcsDir[i][j] = 2;  // 左边
				}						
			}
		}
	return lcsLen[M][N];
}