动态规划作业-最长公共子序列问题

问题：对给定序列X=(x1,x2,...xm)和序列Z=（z1,z2,...zk)，Z是X的子序列当且仅当存在一个递增下标序列（i1,i2,...ik)

使得对于所有j=1,2,,,k有zj=xi_j(1<=xi_j<=m)。例如序列（a,b,c,b,d,a,b）的一个子序列(b,c,d,b)

相应的递增下标序列(2,3,5,7)

给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列

定义子问题：设L(m,n)表示序列X=(x1,x2,...xm和Y=(y1,y2,...yn)的最长公共子序列的长度，显然

初始子问题是序列X和Y至少有一个空序列，即：

L(0,0)=L(0,j)=L(i,0)=0, 1<=i<=m,1<=j<=n

动态规划函数：

L(i,j)=L(i-1,j-1)+1 xi=yj,i>=1,j>=1

L(i,j)=max{(L(i-1,j),L(i,j-1)} xi!=yj,i>=1,j>=1

为了得到序列X和Y的最长公共子序列，设二维表S(m,n)记载求解过程中的状态变化

S(i,j)=1 xi=yj

S(i,j)=2 xi!=yj，L(i,j-1)>=L(i-1,j)

S(i,j)=3 xi!=yj, L(i,j-1)<L(i-1,j)

若S(i,j)=1,则下一个搜索方向是S(i-1,j-1)

若S(i,j)=2,则下一个搜索方向是S(i,j-1)

若S(i,j)=3则下一个搜索方向是S(i-1,j)

算法：

输入：两个序列x和y

输出：最长公共子序列及其长度

1.循环变量i从0到l1重复下列操作

L[i][0]=S[i][0]=0;

2.循环变量i从0到l2重复下列操作

L[0][i]=S[0][i]=0;

3.循环变量i从1到l1重复下列操作

3.1循环变量j从1到l2

3.1.1如果x[i]==y[j]

S[i][j]=1; L[i][j]=L[i-1][j-1]+1

3.1.2否则如果 L[i][j-1]>=L[i-1][j]

S[i][j]=2; L[i][j]=L[i][j-1]

3.1.3否则 S[i][j]=3;L[i][j]=L[i-1][j]

4.使i=l1,j=l2，k=0；直到i<0 或者j<0,用字符数组path记录最长公共子序列

4.1如果S[i][j]==1 path[k++]=x[i],i--,j--;

4.2否则，如果S[i][j]=2 j--;

4.3否则 i--;

void dp_com(char x[], char y[],int l1,int l2) {
    int L[][];
    int S[][];
    char path[];
    for (int i = ; i <=l1; i++)
        L[i][] = S[i][] = ;
    for (int i = ; i <=l2; i++)
        L[][i] = S[][i] = ;
    for (int i = ; i <=l1; i++) {
        for (int j = ; j <=l2; j++) {
            if (x[i] == y[j]) {
                S[i][j] = ;
                L[i][j] = L[i - ][j - ] + ;
            }
            else if (L[i][j-] >=L[i-][j]) {
                S[i][j] = ;
                L[i][j] = L[i][j-];
            }
            else {
                S[i][j] = ;
                L[i][j] = L[i-][j];
            }
        }
    }
    cout << L[l1][l2] << endl;
    int i = l1, j = l2;
    int k = ;
    while (i > && j >) {
        if (S[i][j] == ) {
            path[k++] = x[i];
            i--;
            j--;
        }
        else if (S[i][j] == ) j--;
        else i--;
    }
    for (i = k-; i >= ; i--)
        cout << path[i];
    cout << endl;
}