目录

前言

题目介绍

输入样例:

输出样例:

引入：

理论存在，实践开始！

 两个串的：

 N个串的：

Love is worth years.❤热爱可抵岁月漫长。

前言

QWQ昨天的PTA里面老师布置的实验题，会了两个的最长子序列问题N个的又不会了，搞得我都想放弃了，于是在问了大神正确答案后，我恍然大悟！！！

我是菜鸡：[  DP真难   ：[                                                  

---

题目介绍

 

输入样例:

1
3
ab
bc
cd

输出样例:

0

在开始之前大家可以先自己写一下看一下能不能自己写出来~注意输出的格式哦！

---

引入：

求两个串的最长子序列是最最最最最经典的动态规划的题目但是。。求N个串的我就蒙了，两个我才学会你就给我来这个？？好了好了，不就是动态规划嘛？？                                                  ：》

---

理论存在，实践开始！

---

 两个串的：

不废话，直接dp上答案;

就像是一个路径问题，如果字符串相等那么就等于左上角加一不然就等于左面和上面的最大的那一个！然后输出最后一个就可以了，很好理解！

#include 
#include 
int dp[501][501];
char a1[501];
char b1[501];

void lcs(int a,int b);
void lcs(int a,int b)
{
    int i,j;
    for (i=1;i<=a;i++)
    {
        for (j=1;j<=b;j++)
        {
            if(a1[i-1]==b1[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else if(dp[i-1][j]>dp[i][j-1])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=dp[i][j-1];
        }
    }
}
int main()
{
    while(scanf("%s",a1)!=EOF)
    {
        scanf("%s",b1);
        int m=strlen(a1);
        int n=strlen(b1);
        memset(dp,0,sizeof(dp));
        lcs(m,n);
        printf("%dn",dp[m][n]);
    }
}

---

 N个串的：

#include 
#include 
#define max2(a,b) ((a) > (b) ? (a) : (b))
#define min2(a,b) ((a) < (b) ? (a) : (b))

char s[105][105];
int len[105];
int dp[30005];
int n;

int LCS(int *x)
{
    int a,i,j,b;
    for(i=1; i<=n; i++)
    {
        if(x[i]==0)
        {
            return 0;
        }    //如果当前有字符串的长度为0，则返回0,递归结束条件

        
    }
    a=x[n]-1;
    for(i=n-1; i>=1; i--)
    {
        
        a=a*len[i]+x[i]-1;
    }//建立映射

    if(dp[a]>=0)
    {
        return dp[a];
    }//dp递归结束条件
    
    for(i=2; i<=n; i++)
    {
        if(s[1][x[1]-1]!=s[i][x[i]-1])
        {
            break;
        }  //判断是否所有串的最后一个字符都相等

    }
    if(i>n)  //如果都相等，则最大长度+1
    {
        for(j=1; j<=n; j++)
        {
            x[j]--;
        }
        b=LCS(x)+1;
        for(j=1; j<=n; j++)
        {
            x[j]++;
        }
    }
    
    else//否则，求删去某个字符串的最后一个字符之后得到的最大值
    {
        b=0;
        for(j=1; j<=n; j++)
        {
            x[j]--;
            int t=LCS(x);
            b=max2(t,b);
            x[j]++;
        }
    }
    dp[a]=b;
    return b;
}
int main()
{
    int t,i;
    int m[105];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1; i<=n; i++)
        {
            scanf("%s",s[i]);//二维数组保存每一个串
            len[i]=m[i]=strlen(s[i]);//用len数组和m数组保存每一个串的长度
        }
        memset(dp,-1,sizeof(dp));//dp初始化
        
        printf("%dn",LCS(m)); //求最长
    }
    return 0;
}

Love is worth years.❤
热爱可抵岁月漫长。