I can't explain the code correctly so I just paste it here.

LCS

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。
比如两个串为：

abcicba
abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Code:

//From the internet
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
string a,b;
int dp[1050][1050],mark[1050][1050],la,lb;

void lcs()
{
    int i,j;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=la;i++)
        mark[i][0]=1;
    for(int i=1;i<=lb;i++)
        mark[0][i]=-1;
    for(int i=1;i<=la;i++)
    {
        for(int j=0;j<=lb;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                mark[i][j]=0;
            }
            else if(dp[i-1][j]>=dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                mark[i][j]=1;
            }
            else
            {
                dp[i][j]=dp[i][j-1];
                mark[i][j]=-1;
            }
        }
    }
}

void output(int x,int y)
{
    if(!x&&!y)
        return ;
    if(mark[x][y]==0)
    {
        output(x-1,y-1);
        cout<<a[x-1];
    }
    else if(mark[x][y]==1)
    {
        output(x-1,y);
    }
    else
    {
        output(x,y-1);
    }
}
int main()
{
    while(cin>>a>>b)
    {
        la=a.size();lb=b.size();
        lcs();
        output(la,lb);
        cout<<endl;
    }
    return 0;
}

Code:

//From boctorio
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 1050 ;
int dp[maxn][maxn];
char a[maxn],b[maxn];
int main()
{
    scanf("%s %s",a+1,b+1);
    int n=strlen(a+1),m=strlen(b+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j])    dp[i][j]=dp[i-1][j-1]+1;
            else    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    stack<char> ans;
    while(n>=1&&m>=1)
    {
        if(dp[n][m]==0)    break;
        if(dp[n][m]-dp[n-1][m-1]==1 && dp[n-1][m-1]==dp[n-1][m] && dp[n-1][m-1]==dp[n][m-1])
        {
            ans.push(a[n]);
            n--;
            m--;
        }
        else if(dp[n][m]==dp[n-1][m] && n>1)    n--;
        else if(dp[n][m]==dp[n][m-1] && m>1)    m--;
    }
    while(!ans.empty())
    {
        printf("%c",ans.top());
        ans.pop();
    }
    puts("");
    return 0;
}

You can take part in the tutorial of dp in the 51nod.It's so good!

赏