UVA 1045 最长公共子序列

题目描述：求最长公共子序列

若给定序列X={x1,x2,...,xm},另一序列Z={z1,z2,...,zk},是X的子序列是指存在一个严格递增的下标序列{i1,i2,...,ik}使得对所以j=1,2,...,k有zj=x(ij)

例如Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}

分析：DP的经典题

状态表示：d[i,j]记录序列x(i)和y(j)的最长公共子序列，其中x(i)={x1,x2,...,xi},y(j)={y1,y1,...,yj},原问题最优解为d[len1,len2]

转移方程：i=0或j=0时，d[i][j]=0;

xi=yj时，d[i][j]=d[i-1][j-1]+1;

xi != yj 时，d[i][j]=max( d[i-1][j],d[i][j-1] )

 #include<cstdio>

 #include<cstring>

 int d[][];

 int max(int a,int b)

 {

     return a>b ? a : b;

 }

 int main()

 {

     char rank1[],rank2[];

     int i,j;

     while(gets (rank1+))

     {

         gets(rank2+);

         memset(d,,sizeof(d));

         int len1=strlen(rank1+);

         int len2=strlen(rank2+);

         for(i=; i<=len1; i++)

             for(j=; j<=len2; j++)

             {

                 if(rank1[i]==rank2[j])

                     d[i][j]=d[i-][j-]+;

                 else

                     d[i][j]=max(d[i-][j],d[i][j-]);

             }

         printf("%d\n",d[len1][len2]);

     }

     return ;

 }

巴特西

UVA 1045 最长公共子序列

最新文章

热门文章