给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
1. 4 5 2. acbd 3. abedc
输出样例：
3
思路：
需要求解既是字符串 A 的子序列又是字符串 B 的子序列的最长字符串长度。我们可以使用一个二维数组 dp 来记录状态，其中 dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符中，既是 A 的子序列又是 B 的子序列的字符串的最大长度。
具体的动态规划转移方程如下：
dp[i][j] = max(dp[i][j-1], dp[i-1][j]); if (a[i] == b[j]) { dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1); }
解释：
dp[i][j-1] 表示在字符串 A 的前 i 个字符和 B 的前 j-1 个字符中，既是 A 的子序列又是 B 的子序列的最大长度。
dp[i-1][j] 表示在字符串 A 的前 i-1 个字符和 B 的前 j 个字符中，既是 A 的子序列又是 B 的子序列的最大长度。
如果 a[i] == b[j]，说明当前字符相同，那么可以在前一个状态的基础上加上当前相同的字符，即 dp[i-1][j-1] + 1。
最终的答案即为 dp[n][m]，其中 n 和 m 分别是字符串 A 和 B 的长度。
完整带注释代码：
#include <iostream> using namespace std; #include <algorithm> const int N = 1010; char a[N], b[N]; int dp[N][N]; int main() { // 读取输入数据 int n, m; cin >> n >> m >> a + 1 >> b + 1; // 动态规划填表 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // 状态转移方程：dp[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符中， // 既是 A 的子序列又是 B 的子序列的字符串的最大长度。 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1); } } // 输出结果，最大长度即为 dp[n][m] cout << dp[n][m] << endl; return 0; }
