文件名称：实验5--最长公共子序列 JAVA
文件大小：1KB
文件格式：JAVA
更新时间：2011-03-22 13:58:23
最长公共子序列
1． 掌握动态规划法的设计思想并能熟练运用
2． 强化动手编程的能力
二． 实验内容
用动态规划法求两个序列的最大公共子序列
三． 算法思想
1． 分析可得如下动态规划函数：
① L[0][0]=L[i][0]=L[0][j]=0 （1<=i<=m,1<=j<=n）
②L[i][j]=L[i-1][j-1]+1 (Xi=Yi,I>1,j>1);或者max{L[i][j-1],L[i-1][j]} (Xi!=Yi,i>1,j>1)
2.由此函数，把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段，第1阶段，按照式1计算X1和Yj的最长公共子序列长度L[1][j](1<=j<=n),第2阶段，按照2式计算X2和Yj的最长公共子序列长度L[2][j]（1<=j<=n）,以此类推，最后在第M阶段，计算Xm和Yj的最长公共子序列长度L[m][j] （1<=j<=n）,则L[m][n]就是序列Xm和Yn的最长公共子序列的长度。