实验四报告(共4页).docx

实验四 动态规划算法一、实验目的与要求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，找出X和Y的最长公共子序列。 改进LCS函数，不使用数组b而仅借助数组c本身在O(m+n)时间内构造最长公共子序列。三实验结果四运行结果分析运行结果正确，且运行速度很快，算法很简洁，但是理解上还是有些困难。五程序代码 #includeusing namespace std;int c10241024,