题目大意：
题解：
最长公共子序列模板题，设(dp[i][j])为字符串(A[1...i])与字符串(B[1...j])的最长公共子序列长度，则状态转移方程为：
[dp[i][j] = max{dp[i-1][j-1] + (A[i] == B[j]), dp[i-1][j], dp[i][j-1]}
]
用(pre)数组记录上一个状态，通过递归输出最长公共子序列。
#include <iostream>
#include <string>
using namespace std;
int dp[1010][1010], pre[1010][1010];
string a, b;
void print(int i, int j) {
if (!i || !j) {
return;
}
if (pre[i][j] == 0) {
print(i - 1, j - 1);
cout << a[i];
} else if (pre[i][j] == 1) {
print(i - 1, j);
} else {
print(i, j - 1);
}
}
int main() {
cin >> a >> b;
int lena = a.length(), lenb = b.length();
a = ' ' + a;
b = ' ' + b;
for (int i = 1; i <= lena; ++i) {
for (int j = 1; j <= lenb; ++j) {
if (a[i] == b[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
pre[i][j] = 0;
} else {
if (dp[i - 1][j] >= dp[i][j - 1]) {
dp[i][j] = dp[i - 1][j];
pre[i][j] = 1;
} else {
dp[i][j] = dp[i][j - 1];
pre[i][j] = 2;
}
}
}
}
print(lena, lenb);
return 0;
}