递归和动态规划构造两个字符序列的最长公共字符子序列

    应je朋友要求，所以翻开以前的算法题目，整理了以下，给出主题的递归和非递归(动态规划)实现。如果能有所帮助，甚是欣慰。我们在JE上更需要分享精神。

    je上有位朋友，给我发短信说，"你为什么有段时间每天都写博客发帖子，你在做什么工作?" 其实，我是搞J2EE的。和大家一样都是Java程序员。我想说的是，"学了计算机，做为一名程序员，他会花费大部分时间和电脑，代码相处，他需要不断的学习，他能真正体会到学无止境是一种什么境界...", 所以，在别人眼里，他们有很少的时间出去花天酒地，出去散心，出去享受这个世界的精彩，因此他们是孤独的，他们要想在自己的职业中有所进步，他们必须忍受孤独...

   孤独了怎么办？内心有想法怎么办？和非同行交流，一头雾水，这是什么啊，不懂...和同行交流，最好的平台在哪里? 在社区...

   于是，我便有了一个小小的目标，我喜欢学习，但我更喜欢分享。因为分享，我才会如此快乐。才会如此发现自己的不足和缺点。才会发现他人的优点，他人的品质。

   于是，我更想做一名服务者，服务大家，向大家学习，职业生涯才会充满乐趣，而非枯燥。也许，会某个问题会和大家有所争执， 但请大家明白，一切行为不是针对人，而是问题本身。当然，我会更加规范和约束自己的行为，虚心倾听，诚心交流和分享。

   每位程序员都不容易，他们的思维都是很有创造性的，他们消耗的能量是最多的，所以每位程序员更需要一个和谐，平衡，安宁的环境。

   我相信，在那些高手，大师所达到的境界里，也许技术不是最重要的，最重要的是内在的和谐，内在的思想，学习的方法和分享的精神。


1. 题目： 求两个字符序列的最长公共字符子序列。

2. 问题分析：

   (1) 递推关系分析：

       考虑最长公共子序列如何变为较小的子问题。
       设A = "a0a1...a(i-1)"
         B = "b0b1...b(j-1)"
       且C = "c0c1...c(k-1)"为A和B的最长公共子序列。


       不难证明有以下结论：

      <1> 如果a(i-1) = b(j-1), 则c(k-1) = a(i-1) = b(j-1), 因此，"c0c1...c(k-2)"是"a0a1...a(i-2)"和"b0b1...b(j-2)"
的一个最长公共子序列。

       <2> 如果a(i-1) != b(j-1), 若c(k-1) = a(i-1), 说明"c0c1...c(k-1)"是"a0a1...a(i-2)"和"b0b1...b(j-1)"
的一个最长公共子序列。

       <3> 如果a(i-1) != b(j-1), 若c(k-1) = b(j-1), 说明"c0c1...c(k-1)"是"a0a1...a(i-1)"和"b0b1...b(j-2)"
的一个最长公共子序列。

   (2) 存储及子问题合并
       基本的存储结构需要3个一维数组，分别存放A、B和C字符序列。要找出最长公共子序列，最重要的是存储当前最长公共子序列的长度
和当前公共子序列的长度。 开辟(i+1)*(j+1)二维数组c，用c[i][j]存储"a0a1...a(i-1)"和"b0b1...b(j-1)"最长公共子序列的长度。由上面
的递推关系，计算出c[i][j]的递归程式：


      <1> c[i][j] = 0  (如果i=0或j=0)

      <2> c[i][j] = c[i - 1][j - 1] + 1 (如果i、j>0且a(i-1) = b(i-1))

      <3> c[i][j] = max(c[i][j-1], c[i-1][j]) (如果i、j>0且a(i-1) != b(i-1))
3. 代码

   (1) 动态规划递归代码：

package boke.written;

/**
 * 求两个字符串的最长公共字符子序列
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.07
 * 
 */
public class MaxLenPubSequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String a = "ABCBDAB";
		String b = "BDCABA";
		MaxLenPubSequence mps = new MaxLenPubSequence(a, b);
		mps.process();

	}

	private int n; // 字符串a和b之间较大长度
	private char[] a; // 字符串a
	private char[] b; // 字符串b
	private char[] str; //最长公共子序列
	private int[][] c; // 当前最公共子序列的长度

	/**
	 * 构造方法
	 * 
	 * @param as
	 * @param bs
	 */
	public MaxLenPubSequence(String as, String bs) {
		a = as.toCharArray();
		b = bs.toCharArray();
		n = ((a.length > b.length) ? a.length : b.length);
		c = new int[a.length + 1][b.length + 1];
		str = new char[n];
	}
	
	/**
	 * 输出a和b最长公共子序列
	 */
	public void process() {
		int n = a.length;
		int m = b.length;
		int k = lcsLen(n, m);
		buileLcs(k, n, m);
		
		for (int i = 0; i < str.length; i++) {
			if (str[i] != '\0')
			System.out.print(str[i]);
		}
	}

	/**
	 * 计算最优值
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	private int lcsLen(int i, int j) {
		if (i == 0 || j == 0) {
			c[i][j] = 0;
		} else if (a[i - 1] == b[j - 1]) {
			c[i][j] = lcsLen(i - 1, j - 1) + 1;
		} else {
			int t1 = lcsLen(i, j - 1);
			int t2 = lcsLen(i - 1, j);
			c[i][j] = (t1 > t2 ? t1 : t2);
		}

		return c[i][j];
	}

	/**
	 * 构造最长公共子序列，k,i,j为字母序号
	 * 
	 * @param k
	 * @param i
	 * @param j
	 */
	private void buileLcs(int k, int i, int j) {
		if (i == 0 || j == 0) {
			return;
		}

		if (c[i][j] == c[i - 1][j]) {
			buileLcs(k, i - 1, j);
		} else if (c[i][j] == c[i][j - 1]) {
			buileLcs(k, i, j - 1);
		} else {
			str[k - 1] = a[i - 1];
			buileLcs(k - 1, i - 1, j - 1);
		}
	}

}

  
   (2) 动态规划非递归代码：

  

 package boke.written;

/**
 * 求两个字符串的最长公共字符子序列
 * 
 * @since jdk1.5及其以上
 * @author 毛正吉
 * @version 1.0
 * @date 2010.06.07
 * 
 */
public class MaxLenPubSequence2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String a = "ABCBDAB";
		String b = "BDCABA";
		MaxLenPubSequence2 mps2 = new MaxLenPubSequence2(a, b);
		mps2.lcsLen();
		mps2.buileLcs();

	}

	private int n; // 字符串a和b之间较大长度
	private char[] a; // 字符串a
	private char[] b; // 字符串b
	private char[] str; // 最长公共子序列
	private int[][] c; // 当前最公共子序列的长度

	/**
	 * 构造方法
	 * 
	 * @param as
	 * @param bs
	 */
	public MaxLenPubSequence2(String as, String bs) {
		a = as.toCharArray();
		b = bs.toCharArray();
		n = ((a.length > b.length) ? a.length : b.length);
		c = new int[a.length + 1][b.length + 1];
		str = new char[n];
	}

	/**
	 * 计算最优值
	 */
	public int lcsLen() {
		int n = a.length;
		int m = b.length;
		for (int i = 0; i <= n; i++) {
			c[i][0] = 0;
		}

		for (int j = 0; j <= m; j++) {
			c[0][j] = 0;
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i - 1] == b[j - 1]) {
					c[i][j] = c[i - 1][j - 1] + 1;
				} else if (c[i - 1][j] > c[i][j - 1]) {
					c[i][j] = c[i - 1][j];
				} else {
					c[i][j] = c[i][j - 1];
				}
			}
		}
		return c[n][m];
	}

	/**
	 * 构造最长公共子序列，k,i,j为字母序号
	 * 
	 */
	private void buileLcs() {
		int k;
		int i = a.length;
		int j = b.length;
		
		k = lcsLen();
		while (k > 0) {
			if (c[i][j] == c[i - 1][j]) {
				i = i - 1;
			} else if (c[i][j] == c[i][j - 1]) {
				j = j - 1;
			} else {
				k--;
				str[k] = a[i - 1];
				j = j - 1;
			}
		}
		
		for (int l = 0; l < str.length; l++) {
			if (str[l] != '\0')
			System.out.print(str[l]);
		}
	}

}

评论

2 楼 sun_left 2010-06-28  

楼主前面的一段话真的很诚恳,也希望je,甚至是国内coder之间也能有像楼主所说的那样的氛围.

1 楼 20055294 2010-06-28  

呵呵，楼主也是成都的哇，顶了，顺便学习