C语言（CED）最长公共子序列----动态规划第一题

一、动态规划算法与分治法的异同

相同点：

A、二者均是将待求解的问题分成若干子问题来求解。

B、二者在编写代码的时候，都要用到递归。

不同点：

A、分治法求解的问题，在将问题分成若干子问题之后，其子问题之间是独立存在的，没有相互关联。而动态规划问题划分后得到的子问题之间相互关联。

B、动态规划问题在求解时需要一个表来记录已解决的子问题的答案，从而避免大量的重复计算。动态规划算法适合用于解最优化问题。这就表明这类最优化问题可能有很多解，但不一定都是最优解，而利用本算法找出的解可能还是众多最优解里的一个

二、最优解问题结构性质

最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

重叠子问题：在用递归算法自顶向下解决问题的时候，每次产生的子问题并不总是新问题，有些子问题被反复计算。动态规划算法正式利用这种子问题的重叠性质，对每个子问题只解一次，并将其保存在表格中。

从一般意义上来讲，问题所具有的这两个重要性质是该问题可用动态规划算法求解的基本要素。

三、动态规划问题分析及解决步骤

A、找出最优解的性质，刻画其结构特征。

B、递归定义最优值

C、自底向上计算最优值（最优值只是一个结果，最优解是一个过程）

D、根据得到的信息构造最优解（A-C是动态规划算法的进本步骤，此步在需要求出问题的最优解时才需执行）

好了，有了上面动态规划的基础知识后，我们开始本文的“重头戏”——最长公共子序列。

四、问题描述（问题大意）

子序列：一个给定序列中，删除若干元素后得到的序列，就是该序列的子序列。

公共子序列：如果有两个序列按照上述步骤之后得到的子序列相同，那么这个子序列被称为这两个序列的公共子序列。

例：有如下两个序列

X={A、B、C、B、D、A、B}，Y={B、D、C、A、B、A}

则序列Z={B、C、A}就是二者的公共子序列，那么什么是最长的公共子序列，大家应该知道了吧？

在这里需要说明的是：一个长度为n的序列，它一共有2的n次方个子序列，有(2^n– 1)个非空子序列。大家需要注意的是，这里说的是序列，和原来的顺序有关联，而不是高中所学无序的集合。

下面将按照动态规划算法设计的步骤来设计解决此问题的算法

1、问题结构

上述证明之后，本问题具有最优子结构性质。

2、递归结构

要找出X={x1,x2,...,xm}和Y={y1,y2,...,yn}的最长公共子序列，可按照以下方式递归：

A、当Xm=Yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上Xm（Xm=Yn），即可得X、Y的最长公共子序列。

B、当Xm！=Yn时，则得解决两个子问题：Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列，二者中较长者即为X和Y的最长公共子序列。

由这个递归结构来看，此问题具有子问题重叠性质，例如：在计算X和Y的最长公共子序列时，可能要计算X和Yn-1及Xm-1和Y的最长公共子序列，这两个子问题都包含一个公共子问题，即要计算Xm-1和Yn-1的最长公共子序列。

首先建立子问题最优值的递归关系，用从c[i][j]记录序列Xi和Yi的最长公共子序列的长度。其中，Xi={x1,x2,...,xi};Yj={y1,y2,...,yj}

当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，所以此时c[i][j]=0;

其他情况：

A、i>0;j=0时,c[i][j]=0;

B、i,j>0;Xi=Yj时，c[i][j]=c[i-1][j-1]+1

C、i,j>0;Xi!=Yj时，c[i][j]=max{c[i][j-1],c[i-1][j]}

3、计算最优值

直接利用上述递归式，写出代码。其中X，Y是输入的两个序列， ，b[i][j]记录c[i][j]的值是由哪个子问题的解得来的，这在构造最长公共子序列时要用到。

void LCSLength(int m,int n,char x[],char y[],int c[][50],int b[][50]){int i,j;for(i=1;i<=m;i++)//当j=0时，c[i][j]=0c[i][0]=0;for(j=1;j<=n;j++)//当i=0时，c[i][j]=0c[0][j]=0;for(i=1;i<=m;i++)//对最长公共子序列的长度进行记录for(j=1;j<=n;j++){if(x[i]==y[j])//Xi=Yj的情况{c[i][j]=c[i-1][j-1]+1;//c[i][j]存储Xi和Yj的最长公共子序列的长度b[i][j]=1; //斜向上 //b[i][j]记录c[i][j]的值是由哪个子问题的解得来的}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;//竖直向上}else{c[i][j]=c[i][j-1];b[i][j]=3;//水平向左}}}

4、构造最长公共子序列

用二维数组b快速构造序列X和Y的最长公共子序列。首先从b[m][n]开始，依照其值在数组b中搜索。

A、当在b[i][j]=1时，表示Xi和Yi的最长公共子序列是由Xi-1和Yi-1的最长公共子序列在尾部加上Xi所得到的。

B、当在b[i][j]=2时，表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。

C、当在b[i][j]=3时，表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。

如此，将最长公共子序列打印出来。代码如下：

void LCS(int i,int j,char x[], int b[][50]){if(i==0||j==0)return;if(b[i][j]==1)//表示Xi和Yi的最长公共子序列是由Xi-1和Yi-1的最长公共子序列在尾部加上Xi所得到的{//b[i][j]==1时，表示左斜45°向上，也即这个时候对应的字母时LCS中的一个。LCS(i-1,j-1,x,b);cout<<x[i]<<" ";}else if(b[i][j]==2)//表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。LCS(i-1,j,x,b);else//表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。LCS(i,j-1,x,b);}

所以，上述的所有步骤转变为完整代码如下：

#include<stdlib.h>#include<stdio.h>#include<iostream>using namespace std;int c[50][50];int b[50][50];char x[1000];//存放X字符串char y[1000];//存放Y字符串void LCSLength(int m,int n,char x[],char y[],int c[][50],int b[][50]){int i,j;for(i=1;i<=m;i++)//当j=0时，c[i][j]=0c[i][0]=0;for(j=1;j<=n;j++)//当i=0时，c[i][j]=0c[0][j]=0;for(i=1;i<=m;i++)//对最长公共子序列的长度进行记录for(j=1;j<=n;j++){if(x[i]==y[j])//Xi=Yj的情况{c[i][j]=c[i-1][j-1]+1;//c[i][j]存储Xi和Yj的最长公共子序列的长度b[i][j]=1; //斜向上 //b[i][j]记录c[i][j]的值是由哪个子问题的解得来的}else if(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;//竖直向上}else{c[i][j]=c[i][j-1];b[i][j]=3;//水平向左}}}void LCS(int i,int j,char x[], int b[][50]){if(i==0||j==0)return;if(b[i][j]==1)//表示Xi和Yi的最长公共子序列是由Xi-1和Yi-1的最长公共子序列在尾部加上Xi所得到的{//b[i][j]==1时，表示左斜45°向上，也即这个时候对应的字母时LCS中的一个。LCS(i-1,j-1,x,b);cout<<x[i]<<" ";}else if(b[i][j]==2)//表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同。LCS(i-1,j,x,b);else//表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。LCS(i,j-1,x,b);}int main(){int xn,yn;//XY字符串的大小cout<<"请输入X集合的元素个数："<<endl;cin>>xn;cout<<"请输入X集合的元素："<<endl;int i=0;//用于循环输入X和Y的字符串for(i=1;i<=xn;i++)cin>>x[i];cout<<"请输入y集合的元素个数："<<endl;cin>>yn;cout<<"请输入y集合的元素："<<endl;for(i=1;i<=yn;i++)cin>>y[i];LCSLength(xn,yn,x,y,c,b);cout << "X和Y的最长公共子序列为：";LCS(xn,yn,x,b);cout << endl;int j = 0;int m = 0;printf("b[i][j]中的数字：\n");for (i = 0; i <=xn; i++)for (j = 0; j <= yn; j++){ printf("%d ", b[i][j]);m++;if (m == xn){m = 0;printf("\n");}}m = 0;printf("c[i][j]中的数字：\n");for (i = 0; i <= xn; i++)for (j = 0; j <=yn; j++){printf("%d ", c[i][j]);m++;if (m == xn){printf("\n");m = 0;}}system("pause");return 0;}

把c[i][j]和b[i][j]对应起来之后，得到下图：

从下图中可以看出，用二维数组b[i][j]中的信息可以构建出X和Y的一个最长公共子序列。从b[xn][yn]开始，沿着橘黄色的箭头方向追踪：

A、b[i][j]等于1时，左斜45°向上跳，并且起跳的字母就是LCS的一个成员

B、b[i][j]等于2时，竖直向上跳。

C、b[i][j]等于3时，水平向左跳。

参考：《计算机算法设计与分析·第五版 》王晓东编著