题目描述：
给定两个长度分别为 NN 和 MM 的字符串 AA 和 BB，求既是 AA 的子序列又是 BB 的子序列的字符串长度最长是多少。
第一行包含两个整数 NN 和 MM。
第二行包含一个长度为 NN 的字符串，表示字符串 AA。
第三行包含一个长度为 MM 的字符串，表示字符串 BB。
字符串均由小写字母构成。
输出一个整数，表示最大长度。
1≤N,M≤10001≤N,M≤1000
4 5
acbd
abedc
3代码：
dp:
1 for (int i = 1; i <= n; i++) { 2 for (int j = 1; j <= m; j++) { 3 if (a[i] == b[j]) { 4 f[i][j] = f[i - 1][j - 1] + 1; 5 } else { 6 f[i][j] = max(f[i - 1][j], f[i][j - 1]); 7 } 8 } 9 } 10 cout << f[n][m] << ‘\n‘;
ac:
1 #include <iostream> 2 using namespace std; 3 4 int n,m; 5 char a[1010],b[1010]; 6 int f[1010][1010]; 7 8 int main() 9 { 10 cin >> n >> m; 11 for(int i = 1;i <= n;i++) cin >> a[i]; 12 for(int i = 1;i <= m;i++) cin >> b[i]; 13 14 for(int i = 1; i<=n; i++) 15 for(int j = 1; j <= m;j ++) 16 { 17 if(a[i] == b[j]) f[i][j] = f[i-1][j-1] + 1; 18 else 19 { 20 f[i][j] = max(f[i-1][j], f[i][j-1]); 21 // 最长公共子序列， 倒数第二位不匹配的两种情况， 取最大值 即最长公共 22 } 23 } 24 25 cout << f[n][m] << endl; 26 27 return 0; 28 }
原文：https://www.cnblogs.com/leoaioliabao/p/14631167.html