当前位置：首页 > 第6讲 - - 动态规划专题讲座
因而有递归关系：
q(i)=max(q(j))+1 (a[j]≥a[i],1≤i { max=0; for(j=i+1;j<=n;j++) if(a[i]<=a[j] && q(j)>max) max=q(j); f=max+1; } return f; } (3) 在主函数中依次调用q(n?1),?,q(1)，比较这n?1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。 （4）构造最优解 从序列的第1项开始，依次输出q(i)分别等于lmax,lmax?1,?,1所那就的项a[i]，这就是所求的一个最长非降子序列。 （5）递归实现动态规划程序设计 // 递归实现动态规划 #include { int t,x,lmax; int q(int i); t=time(0)00;srand(t); // 随机数发生器初始化 printf(\ scanf(\ for(i=1;i<=n;i++) {a[i]=rand()%(5*n)+10; // 产生并输出n个数组成的序列 printf(\ } lmax=0; for(i=n-1;i>=1;i--) if(q(i)>lmax) lmax=q(i); // 比较得最大非降序列长 printf(\输出最大非降序列长 x=lmax; for(i=1;i<=n;i++) if(q(i)==x) {printf(\输出一个最大非降序列 } 4．程序运行示例与讨论 运行程序，input n(n<2000):12 48 16 45 47 52 46 36 28 46 69 14 42 L=5. 16 45 47 52 69 注意，所给序列长度为5的非降子序列可能有多个，这里只输出其中一个。 由上可知，在动态规划设计中，最优值可经递推得到，也可经递归得到。一般地，应用递推效率更高些，以下各案例的动态规划设计中均应用递推得最优值。 6.2.2 最长公共子序列 一个给定序列的子序列是在该序列中删去若干个元素后所得到的序列。用数学语言表述， 给定序列X??x1,x2,?,xm?，另一序列Z??z1,z2,?,zk?，X的子序列是指存在一个严格递增 下标序列?i1,i2,?,ik?使得对于所有j=1,2,?,k有zj?xij。例如，序列Z??b,d,c,a?是序列 X??a,b,c,d,c,b,a?的一个子序列，或按紧凑格式书写，序列“bdca”是“abcdcba”的一个 子序列。 若序列Z是序列X的子序列，又是序列Y的子序列，则称Z是序列X与Y的公共子序列。例如，序列“bcba”是“abcbdab”与“bdcaba”的公共子序列。 1. 案例提出 给定两个序列X??x1,x2,?,xm?和Y??y1,y2,?,yn?，找出序列X和Y的最长 公共子序列。 例如，给出序列X：hsbafdreghsbacdba与序列Y：acdbegshbdrabsa，这两个序列的最长公共子序列如何求得？ 2．动态规划算法设计 求序列X与Y的最长公共子序列可以使用穷举法：列出X的所有子序列，检查X的每一个子序列是否也是Y的子序列，并记录其中公共子序列的长度，通过比较最终求得X与Y的最长公共子序列。对于一个长度为m的序列X，其每一个子序列对应于下标集{1,2,?,m}的 m 一个子集，即X的子序列数目多达2个。由此可见应用穷举法求解是指数时间的。 最长公共子序列问题具有最优子结构性质，应用动态规划设计求解。 （1）建立递推关系 设序列X??x1,x2,?,xm?和Y??y1,y2,?,yn?的最长公共子序列为Z??z1,z2,?,zk?， ?xi,xi?1,?,xm?与?yj,yj?1,?,yn?(i=0,1,?,m;j=0,1,?,n)的最长公共子序列的长度为 c(i,j)。 若i=m+1或j=n+1，此时为空序列，c(i,j)=0（边界条件）。 若x(1)=y(1)，则有z(1)=x(1),c(1,1)=c(2,2)+1（其中1为z(1)这一项）； 若x(1)≠y(1)，则c(1,1)取c(2,1)与c(1,2)中的最大者。 一般地，若x(i)=y(j)，则c(i,j)=c(i+1,j+1)+1； 若x(i)≠y(j)，则c(i,j)=max(c(i+1,j),c(i,j+1))。 因而归纳为递推关系： 1≤i≤m,1≤j≤n,xi?yj??c(i?1,j?1)?1c(i,j)?? max(c(i,j?1),c(i?1,j))1≤i≤m,1≤j≤n,x?y?ij? 边界条件：c(i,j)=0 （i=m+1或j=n+1） （2）逆推计算最优值 根据以上递推关系，逆推计算最优值c(0,0)流程为： for(i=0;i<=m;i++) c[i][n]=0; // 赋初始值 for(j=0;j<=n;j++) c[m][j]=0; for(i=m?1;i>=0;i??) // 计算最优值 for(j=n?1;j>=0;j??) if(x[i]==y[j]) c[i][j]=c[i+1][j+1]+1; else if(c[i][j+1]>c[i+1][j]) c[i][j]=c[i][j+1]; else c[i][j]=c[i+1][j]; printf(\最长公共子串的长度为：%d\ // 输出最优值 以上算法时间复杂度为O(mn)。 （3）构造最优解 为构造最优解，即具体求出最长公共子序列，设置数组s(i,j)，当x(i)=y(j)时s(i,j)=1；当x(i)≠y(j)时s(i,j)=0。 X序列的每一项与Y序列的每一项逐一比较，根据s(i,j)与c(i,j)取值具体构造最长公共子序列。实施x(i)与y(j)比较，其中i=0,1,?,m?1;j=t,1,?,n?1；变量t从0开始取值，当确定最长公共子序列一项时，t=j+1。这样处理可避免重复取项。 若s(i,j)=1且c(i,j)=c(0,0)时，取x(i)为最长公共子序列的第1项; 随后，若s(i,j)=1且c(i,j)=c(0,0) ?1时，取x(i)最长公共子序列的第2项; 一般地，若s(i,j)=1且c(i,j)=c(0,0) ?w时(w从0开始，每确定最长公共子序列的一项，w增1)，取x(i)最长公共子序列的第w项。 构造最长公共子序列描述： for(t=0,w=0,i=0;i<=m?1;i++) for(j=t;j<=n?1;j++) if(s[i][j]==1 && c[i][j]==c[0][0]?w) {printf(\ w++;t=j+1;break; } （4）算法的复杂度分析 2 以上动态规划算法的时间复杂度为O(n)。 3．最长公共子序列C程序实现 // 最长公共子序列 #include {char x[N],y[N]; int i,j,m,n,t,w,c[N][N],s[N][N]; printf(\请输入序列x：\// 先后输入序列 scanf(\ printf(\请输入序列y：\ for(m=0,i=0;x[i]!='\\0';i++) m++; for(n=0,i=0;y[i]!='\\0';i++) n++; for(i=0;i<=m;i++) c[i][n]=0; // 赋边界值 for(j=0;j<=n;j++) c[m][j]=0; for(i=m?1;i>=0;i??) // 递推计算最优值 for(j=n?1;j>=0;j??) if(x[i]==y[j]) {c[i][j]=c[i+1][j+1]+1; s[i][j]=1; } else {s[i][j]=0; if(c[i][j+1]>c[i+1][j]) c[i][j]=c[i][j+1]; else c[i][j]=c[i+1][j]; } printf(\最长公共子序列的长度为：%d\// 输出最优值 printf(\最长公共子序列为：\构造最优解 t=0;w=0; for(i=0;i<=m?1;i++) for(j=t;j<=n?1;j++) if(s[i][j]==1 && c[i][j]==c[0][0]?w) {printf(\ w++;t=j+1;break; }
本文作者：...共分享92篇相关文档
