选择题第八题：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int MAXN = 1005; // 假设字符串长度不超过1000
char s1[MAXN], s2[MAXN];
int dp[MAXN]; // 一维DP数组int main() {while (cin >> s1 >> s2) {int n1 = strlen(s1), n2 = strlen(s2);memset(dp, 0, sizeof(dp)); // 初始化dp数组// 遍历s1的每一个字符for (int i = 1; i <= n1; ++i) {int prev = 0; // 保存 dp[j-1] 在更新前的值，即 dp[i-1][j-1]for (int j = 1; j <= n2; ++j) {int temp = dp[j]; // 临时保存当前 dp[j]，用于下一轮 previf (s1[i - 1] == s2[j - 1]) {dp[j] = prev + 1; // 当前字符匹配，继承左上角的值 +1} else {dp[j] = max(dp[j], dp[j - 1]); // 不匹配，取左或上的最大值}prev = temp; // 更新 prev 为当前 dp[j] 的旧值}}cout << dp[n2] << endl; // 最终答案}return 0;
}
空间压缩版参考程序
