最長公共子序列--動態規劃入門 - acm1314－IT工程師數位筆記本

文章出處

求兩個序列 X{1，2， 5， 4，。。。}和Y{1， 5， 4，，，，}中最長的共有序列。例如X = {A，B， C， B，D, A， B}， Y={B，D，C，A，B，A} 兩者的最長公共子序列為 {B，C，B， A}

分析：

這個問題是否可以分成一段一段處理呢？（即可否找出遞歸結構，可見遞歸很重要，也許你感覺它很基礎，其實它很深奧！）。我們從X，Y的最后一個元素來考慮，若X的最后一個元素在最長子串中（即它對最長子串有貢獻），那么有兩種情況，它和Y的最后一個元素相同，或它與Y最后一個對最長子串有貢獻的元素相等（你也許會說，這個SB也知道，但它偏偏很重要）。另 c[i][j] 記錄從 Xi和Yj的公共最長子序列。（這類題都是他媽的，這一個慫樣，不要問我為什么）。

于是乎，關鍵的遞歸公式橫空出世。

當 i= 0，或 j = 0 時， c[i][j ] = 0;

　　　　　　　　當i, j>0, xi = yj 時， c[i][j] = c[i-1][j-1] + 1;

當i,j>0, xi != yj 時， c[i][j] = {c[i][j-1], c[i-1][j]} --->就是由那個SB都知道的東西推來的！！嘿嘿！

#include<iostream>
#include<cstring>
using namespace std;

const int maxn = 100+5;
int b[maxn][maxn];
char x[maxn], y[maxn];
//用b[][]來記錄取得最優值的路徑。 
int lcsLength(char x[maxn], char y[maxn], int b[maxn][maxn])//計算最優解。 
{
    int m = x.length - 1;
    int n = y.length - 1;
    int c[m+1][n+1];
    for(int i=1; i<=m; i++) c[i][0] = 0;
    for(int i=1; i<=n; i++) c[0][i] = 0;
    for(int i=1; i<=m; i++)
    for(int j=1; j<=n; j++)
    {
        if(x[i]==y[j])
        {
            c[i][j] = c[i-1][j-1] + 1;
            b[i][j] = 1;                   
        }
        else if(c[i-1][j]>=c[i][j-1])
        {
            c[i][j] = c[i-1][j];
            b[i][j] = 2;
        }
        else
        {
            c[i][j] = c[i][j-1];
            b[i][j] = 3;
        }
    }
    return c[m][n];
}

//構造最優子序列。
void lcs(int i, int j, char x[maxn], int b[maxn][maxn])
{
    if(i==0||j==0) return;
    if(b[i][j]==1)
    {
        lcs(i-1, j-1, x, b);//又是遞歸， 看到了吧！！ 
        printf("%c", x[i]);
    }
    else if(b[i][j]==2) lcs(i-1, j, x, b);
    else lcs(i, j-1, x, b);
} 

int main()
{
    /* 讀入字符串x,y時從1讀*/
}