题目描述

给定两个长度分别为 N
和 M
的字符串 A
和 B
，求既是 A
的子序列又是 B
的子序列的字符串长度最长是多少。

输入格式
第一行包含两个整数 N
和 M
。

第二行包含一个长度为 N
的字符串，表示字符串 A
。

第三行包含一个长度为 M
的字符串，表示字符串 B
。

字符串均由小写字母构成。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N,M≤1000

输入样例：
4 5
acbd
abedc
输出样例：
3

算法1

dp

#include <iostream>
using namespace std;
const int maxn = 2010;

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

int main()
{

    int m, n;
    cin >> m >> n;
    cin >> a >> b;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
            if (a[i] == b[j])
            {
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            }
        }
    }

    cout << dp[m][n] << endl;
    return 0;
}