nyoj 36 最长公共子序列（Dp）

我就是我 2022-04-01 14:10 224阅读 0赞

## 最长公共子序列 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。  
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

输入

第一行给出一个整数N(0<N<100)表示待测数据组数  
接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
    asdf
    adfsd
    123abc
    abc123abc

样例输出

3
    6

来源

动态规划 动态转移方程dp\[i,j\] = max （dp\[ i-1 , j-1 \]+ same(i,j), dp\[ i-1 \]\[ j \] , dp\[ i \]\[ j-1 \]）;same( i, j ,)中i，j 相同返回1 ，否则返回0；代码：

#include<stdio.h>
    #include<string.h>
    int dp[1200][1200];
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    
    int main()
    {
        memset(dp,0,sizeof(dp));
        char a[1200],b[1200];
        int N,i,j,la,lb,count;
        scanf("%d",&N);
        while(N--)
        {
            scanf("%s",&a);la=strlen(a);
            scanf("%s",&b);lb=strlen(b);
            for(i=1;i<=la;i++)
            {
                for(j=1;j<=lb;j++)
                {
                    if(a[i-1]==b[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];
                }
            }
            printf("%d\n",dp[la][lb]);
        }
        return 0;
    }