一个给定序列的子序列是在该序列中删去若干元素后得到的序列。
问题：给定两个序列X和Y，找出二者的最长公共子序列。

请设计动态规划，备忘录和递归三个算法。
B,C,B,A 　B,D,A,B　B,C,A,B 均正确

动态规划解决：

1、二维数组c[i][j]表示：X的前i个序列，和Y的前j个序列的最长公共子序列的长度
2、数组打底：当其中有一个长度为0的时候，c[i][0]=c[0][j]=0
3、递推式：

#include<stdio.h>
#define M 7   // X的长度
#define N 6   // Y的长度

void LCSLength(char* X,char* Y,int** c,int** b){
    for(int i=0;i<=M;i++){
        c[i][0]=0; //表示Yj为空序列，自然没有公共子序列，赋值为0 
        b[i][0]=1; //表示第一种情况
    }
    for(int i=0;i<=N;i++){
        c[0][i]=0; //表示Xi为空序列，自然没有公共子序列，赋值为0 
        b[0][i]=1; //表示第一种情况 
    }
    
    for(int i=1;i<=M;i++){
        for(int j=1;j<=N;j++){
            if(X[i-1]==Y[j-1]){
                c[i][j]=c[i-1][j-1]+1;
                b[i][j]=2;
            }else if(c[i-1][j]>c[i][j-1]){   //c[i-1][j]是情况3，c[i][j-1]是情况4 
                c[i][j]=c[i-1][j];           //哪个大要哪个！ 
                b[i][j]=3;
            }else{
                c[i][j]=c[i][j-1];           //哪个大要哪个！ 
                b[i][j]=4;
            } 
        }
    }
}

void LCS(char* X,int** b,int m,int n){   //输出最长公共子序列
    if(m==0||n==0){  //要从后往前找,某一个序列找到头了，就结束 
        return;
    }
    if(b[m][n]==1){
        return; 
    }else if(b[m][n]==2){
        LCS(X,b,m-1,n-1);
        printf("%3c",X[m-1]);
    }else if(b[m][n]==3){
        LCS(X,b,m-1,n);
    }else{
        LCS(X,b,m,n-1);
    }   
}

int main(){ 
    char X[M]={'A','B','C','B','D','A','B'};
    char Y[N]={'B','D','C','A','B','A'};
    
    int **c=new int *[M+1];  //c数组表示Xi序列和Yj序列的最长公共子序列长度
    int **b=new int *[M+1];  //b数组表示哪一种子问题解决的 1？2？3？4?
    for(int i=0;i<M+1;i++){
        c[i]=new int[N+1];
        b[i]=new int[N+1];
    } 

    LCSLength(X,Y,c,b);
    printf("最长公共子序列长度为%d\n",c[M][N]);
    LCS(X,b,M,N);
    
    return 0;   
}

运行截图

递归解决：

当数组a和b对应位置字符相同时，则直接求解下一个位置；当不同时取两种情况中的较大数值。
　　只能求个数，不能求出具体的序列

#include<stdio.h>
#define M 7
#define N 6

int LCSLength(char* X,char* Y,int m,int n){
    int temp=0;//记录最长公共子序列的个数 
    if(m<0||n<0)
        return 0;
    if(X[m]==Y[n]){ 
        temp=1+LCSLength(X,Y,m-1,n-1);
    } 
    else{
        int a=LCSLength(X,Y,m-1,n);
        int b=LCSLength(X,Y,m,n-1);
        if(a>b)
            temp+=a;
        else
            temp+=b;
    }
    return temp;
} 
int main(){ 
    char X[M]={'A','B','C','B','D','A','B'};
    char Y[N]={'B','D','C','A','B','A'};
    
    printf("最长公共子序列长度为%d\n",LCSLength(X,Y,M-1,N-1));
    
    return 0;   
}

运行截图

备忘录解决

在递归的基础上改成备忘录是很容易的，无非就是找个数组把过程的值记录下来，每次递归先看这个数有没有被记录。若记录了，直接return，否则计算好，放进数组，再return
　　递归过程中，数组尽量定义成全局的，否则容易溢出导致程序直接死了

#include<stdio.h>
#include<string.h>
#define M 7
#define N 6
int c[M][N];   //定义成全局的，不再递归传递，程序就正常了

int LCSLength(char* X,char* Y,int m,int n){
    if(c[m][n]>0)
        return c[m][n];
    else if(m<0||n<0)
        return 0;
    if(X[m]==Y[n])
        c[m][n]=1+LCSLength(X,Y,m-1,n-1);
    else{
        int a=LCSLength(X,Y,m-1,n);
        int b=LCSLength(X,Y,m,n-1);
        c[m][n]=a>b?a:b;
    }
    return c[m][n];
} 
int main(){ 
    char X[M]={'A','B','C','B','D','A','B'};
    char Y[N]={'B','D','C','A','B','A'};
    memset(c,0,sizeof(c));
    printf("最长公共子序列长度为%d\n",LCSLength(X,Y,M-1,N-1));
    return 0;   
}

运行截图