算法设计例题：最长公共子序列（DP）

时间：2020-12-04 14:42:21 收藏：0 阅读：60

Description

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 X = { x₁，x₂，…，x_m }，则另一序列Z ={ z₁，z₂，…，z_k }，X 的子序列是指存在一个严格递增下标序列{ i₁，i₂，…，i_k }，使得对于所有 j = 1，2，…，k ，有 z_j = x_{i_j}

给出两个字符序列 X 和 Y ，求出它们的最长公共子序列。

Input

输入的第一行为测试样例的个数T，接下来有T个测试样例。每个测试样例的第一行是字符串 X ，第二行是字符串 Y。X 和 Y 只包含大写字母，且长度不大于1000。

Output

对应每个测试样例输出一行，只有一个整数，表示字符串 X 和字符串 Y 的最长公共子序列的长度。

Sample Input

2
ABCDE
ACE
AAABBBCCC
AABBCC

Sample Output

3
6

#include<bits/stdc++.h>
const int maxn = 1e3+10;
using namespace std;
int dp[maxn][maxn];
int main()
{
    int t;cin>>t;
    while(t--){
        string s,ss;
        cin>>s>>ss;
        int l=s.size(),ll=ss.size();
        for(int i=0;i<l;i++)
            for(int j=0;j<ll;j++){
                if(s[i]!=ss[j])
                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
                else dp[i+1][j+1]=dp[i][j]+1;
            }
        cout<<dp[l][ll]<<endl;
    }
}

原文：https://www.cnblogs.com/JAJA-Xin/p/14085370.html