HDU 1159 Common Subsequence --- DP入门之最长公共子序列

题目链接

基础的最长公共子序列

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e3+;

char c[maxn],d[maxn];

int dp[maxn][maxn];

int main()

{

    while(scanf("%s%s",c,d)!=EOF)

    {

        memset(dp,,sizeof(dp));

        int n=strlen(c);

        int m=strlen(d);

        for(int i=;i<n;i++)

        for(int j=;j<m;j++)

        if(c[i]==d[j])

        dp[i+][j+]=dp[i][j]+;

        else

        dp[i+][j+]=max(dp[i+][j],dp[i][j+]);

        printf("%d\n",dp[n][m]);

    }

    return ;

}

再附上一个既可以输出长度也可以输出字符串的代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=1e3+;

char s1[maxn],s2[maxn];

int b[maxn][maxn],dp[maxn][maxn];

void pr(int i,int j)

{

    if(i==||j==) return ;

    if(b[i][j]==)

    {

        pr(i-,j-);

        printf("%c",s1[i]);

    }

    else if(b[i][j]==) pr(i-,j);

    else pr(i,j-);

}

int main()

{

    while(scanf("%s%s",s1,s2)!=EOF)

    {

        memset(b,,sizeof(b));

        memset(dp,,sizeof(dp));

        int len1=strlen(s1),len2=strlen(s2);

        for(int i=len1;i>=;i--) s1[i]=s1[i-];//这里注意不要写成从前往后跑的

        for(int i=len2;i>=;i--) s2[i]=s2[i-];

        for(int i=;i<=len1;i++)

        for(int j=;j<=len2;j++)

        {

            if(s1[i]==s2[j])

            {

                dp[i][j]=dp[i-][j-]+;

                b[i][j]=;

            }

            else if(dp[i-][j]>dp[i][j-])

            {

                dp[i][j]=dp[i-][j];

                b[i][j]=;

            }

            else

            {

                dp[i][j]=dp[i][j-];

                b[i][j]=;

            }

        }

        //这个是长度

        //printf("%d\n",dp[len1][len2]);

        //这个是LCS序列

        pr(len1,len2);

        puts("");

    }

    return ;

}