算法起步之动态规划LCS

原文:算法起步之动态规划LCS

            前一篇文章我们了解了什么是动态规划问题，这里我们再来看动态规划另一个经典问题，最长公共子序列问题（LCS），什么是子序列，我们定义：一个给定序列将其中的0个或者多个元素去掉之后得到的序列就是他的子序列。例如序列x包含（a,b,c,b,d,a,b）那么序列y(b,c,d,b)就是x的一个子序列。公共子序列则是两个序列的公共的子序列，而最长公共子序列则是从两个序列的公共子序列中挑选出长度最长的子序列。

           我们用我们说的动态规划的四步来分析这个问题。一刻画最长公共子序列的特征。假设序列X（包含X1，X2……Xm）而序列Y（Y1……Yn）而他们的最长公共子序列为Z（Z1……Zk）；那么1如果Xm=Yn则Zk-1是Xm-1与Yn-1的最大公共子序列。2如果Xm！=Yn且Zk！=Xm那么Zk是Xm-1与Yn的最大公共子序列。3如果Xm！=Yn且Zk！=Yn那么Zk是Xm与Yn-1的最大公共子序列。通过这3种情况我们就可以将我们刚才的问题刻画成一个递归的问题。

        我们可以通过递归的方式来求出最长公共子序列的长度。然后我们采用自底向上的方法来求出最优解。

public void lcsLength(String x,String y){
		int xl=x.length();
		int yl=y.length();
		int[][] map=new int[xl+1][yl+1];
		for (int i = 1; i <=xl; i++) {
			for (int j = 1; j <=yl; j++) {
				if (x.charAt(i-1)==y.charAt(j-1)) {
					map[i][j]=map[i-1][j-1]+1;
				}else {
					if(map[i-1][j]>map[i][j-1]){
						map[i][j]=map[i-1][j];
					}else {
						map[i][j]=map[i][j-1];
					}
				}

			}
		}
		System.out.println(map[xl][yl]);
	}

	public static void main(String[] args) {
		new LCS().lcsLength("abcab", "bcadd");
	}

           这个图是一个例子运行时数组中值得变化，大家看了这个图应该比较清楚。

           这样我们就求得了最长公共子序列的长度，然后我们可以根据改进算法把最长公共子序列打印出来。当然这里改进的方法有太多了，每个人可能都有自己的想法，我只提供一种方法供大家参考（并没有考虑运行效率等因素）：

public class LCS {
	private StringBuffer sb=new StringBuffer();
	private int ox=0;
	private int oy=0;
	public void lcsLength(String x,String y){
		int xl=x.length();
		int yl=y.length();
		int[][] map=new int[xl+1][yl+1];
		for (int i = 1; i <=xl; i++) {
			for (int j = 1; j <=yl; j++) {
				if (x.charAt(i-1)==y.charAt(j-1)) {
					map[i][j]=map[i-1][j-1]+1;
						if (i>ox&&j>oy) {
							if(map[i][j]>sb.length()){
							sb.append(x.charAt(i-1));
							ox=i;oy=j;
							}
						}else {
							if (i>ox&&j<oy&&map[i][j]==sb.length()) {
								sb.deleteCharAt(sb.length()-1);
								sb.append(x.charAt(i-1));
								ox=i;oy=j;
							}
						}
				}else {
					if(map[i-1][j]>map[i][j-1]){
						map[i][j]=map[i-1][j];
					}else {
						map[i][j]=map[i][j-1];
					}
				}
			}
		}
		System.out.println(map[xl][yl]);
		System.out.println(sb.toString());
	}

	public static void main(String[] args) {
		new LCS().lcsLength("abcab", "bcadd");

	}

}

友情提示：转载请注明出处【作者：idlear  博客：http://blog.csdn.net/idlear】