动态规划解最长公共子序列问题

动态规划解最长公共子序列问题动态规划主要针对最优化问题，它的决策是全面考虑不同的情况分别进行决策，，最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后，会不断决策出新的数据，直到找到最优解.每次决策依赖于当前状态，又随机引起状态的转移.一个决策序列就是在变化的状态中产生出来的，故有”动态”的含义.所以，这种多阶段最优化决策解决问题的过程称为动态规划.一问题的描述与分析字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干字符（可能一个也不去掉）后形成的字符序列..令给定的字符序列X="x0，x1，x2，„xm-1”，序列Y="y0，y1，…yk-广是X的子序列，存在X的一个严格递增下标序列i=i0，i1，i2，„ik-1，使得对所有的j=0，1，2，„k-1，有xi=yi。例如X="ABCBDAB”，Y=“BCDB^是X的一个子序列。给定两个序列A和B，称序列Z是A和B公共子序列，是指Z同是A和B的子序列。求最长公共子序列。若A的长度为m，B的长度为n，则A的子序列有2*m-1个，B的子序列有2*n-1个。采用枚举法分别对A和B的所以子序列一一检查，最终求出最长公共子序列。如此比较次数（2*2n）接近指数阶，当n较大时，算法太耗时，不可取。所以要全面考虑不同的情况分别进行决策,，最后通过多阶段决策逐步找出问题的最终解.当各个阶段采取决策后，会不断决策出新的数据，直到找到最优解。二、算法设计（或算法步骤）A=''a0，a1，a2,……am-1''，B=''b0，b1，b2,……bn-1”，且Z=''z0，z1，z2……zk-1''，为她们的最长公共子序列。不难证明有一下结论：（1） 如果am-1=bn-1，则zk-1=am-1=bn-1,且“z0,z1,z2, zk-2”是“a0,a1,a2, am-2”和“b0,b1,b2,……bn-2”的一个最长公共子序列；（2） 如果am-1!=bn-1,则若zk-1!=am-1,则“z0,z1,z2, zk-1”是“a0,a1,a2, am-2”和”b0,b1,b2,……bn-1”的一个最长公共子序列。（3） 如果am-1!=bn-1,则若zk-1!=bn-1,则“z0,z1,z2, zk-1”是“a0,a1,a2, am-1”和“b0,b1,b2,……bn-2”的一个最长公共子序列。如此找到了原问题与其子问题的递归关系。基本存储结构是存储两个字符串及其最长公共子序列的3个一位数组。当然要找出最长公共子序列，要存储当前最长公共子序列的长度和当前公共子序列的长度，而若只存储当前信息，最后只能求解最长公共子序列的长度，却不能找到最长公共子序列本身。因此需建立一个（n+1）*（m+1）的二维数组c,c[i][j]存储序列“a0,a1,a2……ai-2”和“b0,b1,……bj-1”的最长公共子序列长度，由上递推关系分析，计算c[i][j]可递归的表述如下：(1)c[i][j]=0如果i=0或j=0;(1)c[i][j]=0c[i][j]=c[i-1][j-1]+1 如果i,j>0,且a[i-1]=b[j-1]c[i][j]=max(c[i][j-1],c[i-1][j]) 如果i,j>0,且a[i-1]!=b[j-1]以此可写出计算两个序列的最长公共子序列的长度函数，最终求解出c[m][n].三、算法实现由二维数组c的递归定义，c[i][j]的结果仅依赖于c[i-1][j-1],c[i-1][j]和c[i][j-1].可以从c[m][n]开始，跟踪c[i][j]结果的产生过程，从而逆向构造最长公共子序列。include<stdio.h>include<string.h>#defineN100/*字符串的最大长度限制*/chara[N],/*第一个字符串*/b[N],/*第二个字符串*/str[N];/*用于存放a与b的公共子序列*//*计算两个序列的最长公共子序列的长度*/intlcs_len(char*a,char*b,intc[][N])(intm=strlen(a),/*计算两个序列的长度*/n=strlen(b),i,/*行指针*/j;/*列指针*/for(i=0;i<=m;i++)c[i][0]=0;/*j==0表示b串长度为0，无论a串多长，两者的公共子序列长度为0*/for(j=1;j<=n;j++)c[0][j]=0;/*根据上一个类推*/for(i=1;i<=m;i++)/*开始递推*/for(j=1;j<=n;j++)/*若两序列的最后一个字符相同，那么公共子序列长度为去掉这最后一个字符后新生成的两个串的公共子序列长度+1*/if(a[i-1]==b[j-1]){c[i][j]=c[i-1][j-1]+1;printf("\nc[%d][%d]=c[%d-1][%d-1]+1\n",i,j,i,j);}/**/elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];printf("\nc[%d][%d]=c[%d-1][%d]\n",i,j,i,j);}/*若两序列最后一个字符不同，那么他们最大子序列的长度为c[i-1][j]和c[i][j-1]中较大的一个*/else{c[i][j]=c[i][j-1];printf("\nc[%d][%d]=c[%d][%d-1]\n",i,j,i,j);}/*调试：将生成的数组方阵显示出来,m行，n列*/printf("\n");printf("");for(j=0;j<=n;j++)printf("%d,",j);/*显示列标号*/printf("\n");for(i=0;i<=m;i++){printf("%d:",i);/*显示行标号*/for(j=0;j<=n;j++)printf("%d,",c[i][j]);printf("\n");/*一行显示完，换下一行*/}returnc[m][n];/*结果：a与b的最大子序列长度存在c[m][n]中*/}/*构造最长子序列函数*/char*build_lcs(chars[],char*a,char*b){/*根据lcs_len()函数计算的结果，倒推出最长子序列，结果放在、[]中*/intk,/*a与b最长子序列的长度*/i=strlen(a),/*a串长度*/j=strlen(b),/*b*/c[N][N];/*存放全部的计算过程，动态规划，体现在这个地方，中间计算结果都在这里*/k=lcs_len(a,b,c);/*将c□□传给lcs_len()计算并求出长度，将中间结果放在c[][]中*/s[k]='\0';/*s串的结束标记*/while(k>0)/*开始倒推*/if(c[i][j]==c[i-1][j])i--;elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];/*将一个公共字符存入s中*/i--;j--;}returns;}/*测试程序*/voidmain(){printf("Entertwostring(<%d)!\n",N);scanf("%s%s",a,b);printf("LCS=%s\n",build_lcs(str,a,b));以X=”ABCBDAB”与Y=”BDCABA”为例，两字符串算法实现求解最长公共子序列的长度和最长公共子序列的求解过程。0I23456yjBDCABA0000000..QJJJ\<10\*~1T\0TTJiT..0\tr:\—3QTt?r0Tr&ntfend0\44CDABEntertwostring(<100)!a,b,ca,b,c,dc[1][1]=c[1-1][1-1]+1c[1][2]=c[1][2-1]c[1][3]=c[1][3-1]c[1][4]=c[1][4-1]c[1][5]=c[1][5-1]c[1][6]=c[1][6-1]c[2][2]=c[2-1][2-1]+1c[2][3]=c[2][3-1]c[2][4]=c[2-1][4-1]+1c[2][5]=c[2][5-1]c[2][6]=c[2-1][6-1]+1c[2][7]=c[2][7-1]c[3][1]=c[3-1][1]c[3][2]=c[3-1][2]c[3][3]=c[3-1][3-1]+1c[3][4]=c[3][4-1]c[3][5]=c[3][5-1]c[3][6]=c[3][6-1]c[3][7]=c[3][7-1]c[4][1]=c[ 4 - 1 ][1]c[4][2]=c[ 4 - 1 ][2-1]+ 1c[4][3]=c[ 4 - 1 ][3]c[4][4]=c[ 4 - 1 ][4-1]+ 1c[4][5]=c[4][5-1]c[4][6]=c[4-1][6-1]+1c[4][7]=c[4][7-1]

c[5][3]=c[5-1][3]c[5][4]=c[5-1][4]c[5][5]=c[5-1][5-1]+1c[5][6]=c[5][6-1]c[5][7]=c[5][7-1]0123450,1,2,3,4,5,6,7,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,012345LCS=a,b,cPressanykeytocontinueEntertwostring(<100)!w，e,r,t,yw,r,t,ec[1][1]=c[1-1][1-1]+1TOC\o"1-5"\h\zc[1][2] = c[ 1][ 2 -1]c[1][3] = c[ 1][ 3 -1]c[1][4] = c[ 1][ 4 -1]c[1][5] = c[ 1][ 5 -1]c[1][6] = c[ 1][ 6 -1]c[1][7] = c[ 1][ 7 -1]c[2][3 ] =c[2][3- 1]c[2][4 ] =c[2-1][ 4- 1 ]+ 1c[2][5 ] =c[2][5- 1]c[2][6 ] =c[2-1][6- 1 ]+ 1c[2][7 ] =c[2][7- 1]c[3][1 ] =c[3-1 ][ 1 ]c[3][2 ] =c[3-1 ][ 2 ]c[3][3 ] =c[3-1 ][ 3 ]c[3][4 ] =c[3-1 ][ 4 ]c[3][5 ] =c[3-1 ][ 5 ]c[3][6 ] =c[3-1 ][ 6 ]c[3][7 ] =c[3-1 ][ 7 - 1 ]+ 1c[4][1 ] =c[4-1 ][ 1 ]c[4][2 ] =c[4-1 ][ 2 - 1 ]+ 1c[4][3 ] =c[4-1 ][ 3 ]c[4][4 ] =c[4-1 ][ 4 - 1 ]+ 1c[4][5]=c[4][5-1]c[4][6 ] =c[4-1 ][ 6 - 1 ]+ 1c[4][7 ] =c[4-1 ][ 7 ]c[5][1 ] =c[5-1 ][ 1 ]c[5][4 ] =c[5-1][ 4]c[5][5 ] =c[5-1][ 5]c[5][6]=c[5-1][6]c[5][7 ] =c[5-1][ 7]c[6][1 ] =c[6-1][ 1]c[6][2 ] =c[6-1][ 2- 1 ]+ 1c[6][3 ] =c[6-1][ 3]c[6][4 ] =c[6-1][ 4- 1 ]+ 1c[6][5 ] =c[6][5- 1]c[6][6 ] =c[6-1][ 6- 1 ]+ 1c[6][7 ] =c[6][7- 1]c[7][1 ] =c[7-1][ 1]c[7][2 ] =c[7-1][ 2]c[7][3 ] =c[7-1][ 3]c[7][4 ] =c[