最长公共子序列问题：
????????下面的简单问题说明了动态规划的基本原理。在字母表一∑上，分别给出两个长度为n和m的字符串A和B，确定在A和B中最长公共子序列的长度。这里，A = a?a?...an。的子序列是一个形式为a?ka?k...aik的字符串，其中每个i都在1和n之间,并且1<i?< i?<…<ik≤n。例如，如果∑= {x, y,z},A = zxyxyz和B= xyyzx，那么xzy 同时是A和B的长度为3的子序列。然而，它不是A和B最长的公共子序列，因为字符串xyyz也是A和B公共的子序列，由于这两个字符串没有比4更长的公共子序列，因此，A和B的最长的公共子序列的长度是4
????????解决这个问题的-一种途径是蛮力搜索的方法:列举A所有的2^n个子序列，对于每一个子序列在O( m)时间内来确定它是否也是B的子序列。很明显，此算法的时间复杂性是O时间复杂度(m22)，是指数复杂性的。
????????为了使用动态规划技术，我们首先寻找--个求最长公共子序列长度的递推公式，令A = a?a?...an和B= b?b?...bm，令L[i,j]表示a?a?...ai和b?b?...bj的最长公共子序列的长度。
????????注意、i和j可能是0，此时，a?a?...ai和b?b?...bj中的一个或同时可能为空字符串。即如果i =0或 j =o，那么L[i,j]=0。很容易证明下面的观察结论。
????????如果i和j都大于0，那么
? ? ? ? 1.若ai=bj, L[i,j]= L[ i-1,j - 1]+1;
·? ? ? ? 2.若ai≠bj, L[i,j ]= max{L[i,j - 1],L[ i- 1,j] }。
最长公共子序列算法伪码：
?
?最长公共子序列公式：
?
?最长公共子序列解题思想：
A的长度为5 B的长度为7
A字符串：zxyyz
B字符串：zyxzyxz
0 z y x z y x z
0 0 0 0 0 0 0 0 0
z 0 0 0 0 0 0 0 0
x 0 0 0 0 0 0 0 0
y 0 0 0 0 0 0 0 0
y 0 0 0 0 0 0 0 0
z 0 0 0 0 0 0 0 0
z与z相遇即相等，将左上角+1，并将其余的比较大小，1>0，所以将其他的值变为1,即得到下图↓
0 z y x z y x z
0 0 0 0 0 0 0 0 0
z 0 1 1 1 1 1 1 1
x 0 1 1 1 1 1 1 1
y 0 1 1 1 1 1 1 1
y 0 1 1 1 1 1 1 1
z 0 1 1 1 1 1 1 1
x与x相遇即相等，y与y相遇即相等，将左上角+1得2，并将其余的比较大小，2>1，所以将其他的值变为2,即得到下图↓
0 z y x z y x z
0 0 0 0 0 0 0 0 0
z 0 1 1 1 1 1 1 1
x 0 1 1 2 2 2 2 2
y 0 1 2 2 2 2 2 2
y 0 1 2 2 2 2 2 2
z 0 1 2 2 2 2 2 2
z与z相遇即相等，y与y相遇即相等，将左上角+1得3，并将其余的比较大小，3>2，所以将其他的值变为3,即得到下图↓
0 z y x z y x z
0 0 0 0 0 0 0 0 0
z 0 1 1 1 1 1 1 1
x 0 1 1 2 2 2 2 2
y 0 1 2 2 2 3 3 3
y 0 1 2 2 2 3 3 3
z 0 1 2 2 3 3 3 3
z与z相遇即相等，将左上角+1得4，没剩余得值了，所以退出程序不用比较,即得到下图↓
0 z y x z y x z
0 0 0 0 0 0 0 0 0
z 0 1 1 1 1 1 1 1
x 0 1 1 2 2 2 2 2
y 0 1 2 2 2 3 3 3
y 0 1 2 2 2 3 3 3
z 0 1 2 2 3 3 3 4
核心代码就那几行：
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else
c[i][j]=max(c[i][j-1],c[i-1][j]);
}
}将数据一步一步的带入代码就可以理解了！
?代码实现：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
void lcs();
int max(int a,int b);
int main()
{
lcs();
return 0;
}
int max(int a,int b)
{
return a>b?a:b;
}
void lcs()
{
int n,m,i,j;
char *a,*b;
printf("分别输入A和B的长度:");
scanf("%d%d",&n,&m);
a=(char *)malloc(n*sizeof(char));
b=(char *)malloc(n*sizeof(char));
int c[n+1][m+1];
printf("输入A字符串：");
scanf("%s",a);
getchar();
printf("输入B字符串：");
scanf("%s",b);
for(i=0;i<=n;i++)c[i][0]=0;
for(j=0;j<=m;j++)c[0][j]=0;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if(a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else
c[i][j]=max(c[i][j-1],c[i-1][j]);
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
printf("%d ",c[i][j]);
}
printf("\n");
}
printf("\n%d\n",c[n][m]);
printf("按任意键继续\n");
}结果实现：?
?
希望这对你有帮助！?
?