动态规划
//求解最长公共子序列问题
#include<stdio.h>
#include<string.h>
#define N 30
int lcslength(char *a,char *b,int c[][N]){ //求c[m][n] 即最长公共子序列的长度
int m = strlen(a),n = strlen(b);
int i,j;
for(i=0;i<=m;i++)
c[i][0] = 0;
for(i=0;i<=n;i++)
c[0][i] = 0;
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(a[i-1] == b[j-1])
c[i][j] = c[i-1][j-1] + 1;
else{
if(c[i-1][j] >= c[i][j-1])
c[i][j] = c[i-1][j];
else
c[i][j] = c[i][j-1];
}
}
}
return c[m][n]; //c[m][n] 即为最长公共子序列的长度
}
char *buildcls(char *a,char *b){ //求a,b的最长公共子序列 即字符数组s[]
int k,i = strlen(a),j = strlen(b);
int c[N][N];
k = lcslength(a,b,c); //调用lcslength()函数，返回最长公共子序列的长度
static char s[N]; //s[]保存a,b的最长公共子序列
s[k] = ' '; //0~k-1
while(k>0){
if(c[i][j] == c[i-1][j])
i--;
else if(c[i][j] == c[i][j-1])
j--;
else{
s[--k] = a[i-1]; // k = k-1 s[k-1] = a[i-1]
i--;
j--;
}
}
return s;
}
int main(){
char X[] = "abcbdb";
char Y[] = "acbbabdbb";
printf("X:%s
",X);
printf("Y:%s
",Y);
printf("X,Y的最长公共子序列为%s
",buildcls(X,Y));
return 0;
}