题目描述

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

输入格式

第一行包含两个整数$N$和$M$

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

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

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

输出格式

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

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

时间复杂度

$O(n^2)$

C++ 代码

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
    cin >> n >> m >> a + 1 >> b + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                //找到一个公共字符，故长度加1
                f[i][j] = f[i - 1][j - 1] + 1;
            } else {
                //没找到则找到临近最大的一个长度，表示最大长度还没有变化
                //【为什么只需要找临近呢？因为dp数组中抽象地保存之前的状态，所以已经包含前面比较短的情况，再者，因为保存之前的状态，现在遍历到的这个位置，临近的元素就是之前状态的长度，因为我现在需要长度不变，所以在临近找一个最大的即可。】
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
        }
    }
  cout << f[n][m] << '\n';
  return 0;
}

算法思想

应用动规的思想，使用一个dp数组来保存状态，dp[i][j]表示字符串A的前i个数中，字符串B对前j个数中公共子序列最长的长度。这里的要解决的子问题是经过A和B中的前i个字符和前j个字符中子序列最长的长度。只要寻找到两个序列中有相等的字符，就说明长度要加1，否则说明目前i、j当前指向的元素还没有找到公共的序列，此时长度不需要增加，只需要找到邻近元素中长度最长那个即可。