本文共 1747 字，大约阅读时间需要 5 分钟。

题意：先给两个水果的名字然后得出一个最短的序列包含这两个词。

思路：我一开始的思路是先求出最长公共子序列，然后做一些处理将其他的部分输出来：两种水果的字符串和最长公共子序列的字符串这三个字符串做对比，当他们三个相同的时候将最长公共子序列里面的字符去掉，如果不相同，将水果中的字符串中的字符去掉直到相同为止，不过网上用了一个好像比较方便的方法，在输出最长公共子序列的路径时候也能输出其他的字符(利用递归回溯)。

注意：网上有一个求最长公共子序列的过程的二维的图值得一看，方便理解！！

我的方法:

//最长公共子序列记录路径#include
   
    #include
    
     char a[110],b[110],e[110];int book[110][110],c[110][110],s=0,b1[110],b2[110];void dfs(int i,int j){    if(c[i][j]==1)//公共部分    {        dfs(i-1,j-1);        e[s++]=a[i-1];    }    else if(c[i][j]==2)//左    {        dfs(i,j-1);    }    else if(c[i][j]==3)//上    {        dfs(i-1,j);    }}int main(){    while(~scanf("%s%s",a,b))    {        s=0;        memset(e,'\0',sizeof(e));        memset(book,0,sizeof(book));        memset(c,0,sizeof(c));        int i,j,k,w;        for(i=0; a[i]!='\0'; i++)        {            for(j=0; b[j]!='\0'; j++)            {                if(a[i]==b[j])//左上                {                    i=i+1;                    j=j+1;                    book[i][j]=book[i-1][j-1]+1;                    c[i][j]=1;                    i=i-1;                    j=j-1;                }                else if(book[i+1][j]>book[i][j+1])//左                {                    i=i+1;                    j=j+1;                    book[i][j]=book[i][j-1];                    c[i][j]=2;                    i=i-1;                    j=j-1;                }                else                {                    i=i+1;                    j=j+1;                    book[i][j]=book[i-1][j];//上                    c[i][j]=3;                    i=i-1;                    j=j-1;                }            }        }        dfs(i,j);        e[s]='\0';        char x[220];        w=0,k=0;        memset(x,'\0',sizeof(x));        for(int i=0; i