1、实验三 动态规划算法一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列 X=x1,x2,xm，则另一序列 Z=z1,z2,zk，是 X 的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有 j=1,2,k 有：zj=xij 。例如，序列Z=B， C，D，B 是序列 X=A，B，C，B ，D ，A，B的子序列，相应的递增下标序列为2，3，5，7。给定 2 个序列 X 和 Y，当另一序列 Z 既是 X 的子序列又是 Y 的子序列时，称 Z 是序列 X和 Y 的公共子序列。给定 2 个序列 X=x1,x2,xm和 Y=y1,y2,yn，找出
2、 X 和 Y 的最长公共子序列。 三、实验步骤程序代码：package unit1;public class LCS public static void main(String args) char x = ,A,B,C,B,D,A,B;char y = ,B,D,C,A,B,A;int b = new intx.lengthy.length;int c = new intx.lengthy.length;lcs(x,y,b,c);lcs_put(x.length-1,y.length-1,x,b);static int lcs(char x,char y,int b,int c)int i
3、,j;int m = x.length - 1;int n = y.length - 1; for(i = 1;i = cij-1)cij = ci-1j;bij = 2;elsecij = cij-1;bij = 3;return cmn;static void lcs_put(int i,int j,char x,int b)if(i = 0 | j = 0 )return;if(bij = 1)lcs_put(i-1,j-1,x,b);System.out.print(xi + “ “ ); else if(bij = 2)lcs_put(i-1,j,x,b);elselcs_put(i,j-1,x,b);四、实验运行结果五、实验心得体会在做本次试验之前，自己对动态规划法不是非常的理解，后来结合课本看了利用动态规划法求最长公共子序列的基本步骤和具体例子之后，自己基本上掌握了动态规划法的基本原理，课本上所列举的利用动态规划法最长公共子序列的代码很简单，懂得规划法解最长公共子序列的基本原理之后吗，结合课本所提供的相关代码编码完成本次试验内容也是很容易，实现起来也很顺利。
