板子。
但是输出方案很烦。
所以记录从哪个状态转移而来。

于是写出了如下代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3015;
int n, m;
int dp[N][N];
pair<int, int> pre[N][N];
char a[N], b[N];
char stk[N], top = 0;
int main() {
    scanf(" %s %s", (a + 1), (b + 1));
    n = strlen(a + 1), m = strlen(b + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (dp[i - 1][j] > dp[i][j]) pre[i][j] = make_pair(i - 1, j), dp[i][j] = dp[i - 1][j];
            if (dp[i][j - 1] > dp[i][j]) pre[i][j] = make_pair(i, j - 1), dp[i][j] = dp[i][j - 1];
            if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j])
                pre[i][j] = make_pair(i - 1, j - 1), dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    int x = n, y = m;

    while (x && y) {
        if (a[x] == b[y]) stk[++top] = a[x];
        auto p = pre[x][y];
        x = p.first, y = p.second;
    }
    while (top) putchar(stk[top--]);
    return 0;
}

喜提 WA。
hack：

abbbbb
aab

所以需要判断一个状态是否有贡献，而不是判断两个位置是否相同。

#include <bits/stdc++.h>
using namespace std;
const int N = 3015;
int n, m;
int dp[N][N];
struct node {
    int x, y;
    bool put;
} pre[N][N];
char a[N], b[N];
char stk[N], top = 0;
int main() {
    scanf(" %s %s", (a + 1), (b + 1));
    n = strlen(a + 1), m = strlen(b + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (dp[i - 1][j] > dp[i][j]) pre[i][j] = (node){i - 1, j, 0}, dp[i][j] = dp[i - 1][j];
            if (dp[i][j - 1] > dp[i][j]) pre[i][j] = (node){i, j - 1, 0}, dp[i][j] = dp[i][j - 1];
            if (a[i] == b[j] && dp[i - 1][j - 1] + 1 > dp[i][j])
                pre[i][j] = (node){i - 1, j - 1, 1}, dp[i][j] = dp[i - 1][j - 1] + 1;
        }
    int x = n, y = m;
    while (dp[x][y] > 0) {
        auto p = pre[x][y];
        if (p.put) stk[dp[x][y]] = a[x];
        x = p.x, y = p.y;
    }
    printf("%s\n", stk + 1);
    return 0;
}

然后我意识到似乎不需要记录任何信息，直接倒着还原就可以了。

#include <bits/stdc++.h>
using namespace std;
const int N = 3015;
int n, m;
int dp[N][N];
char a[N], b[N];
char stk[N];
int main() {
    scanf(" %s %s", (a + 1), (b + 1));
    n = strlen(a + 1), m = strlen(b + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (a[i] == b[j]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    int x = n, y = m;
    while (dp[x][y] > 0) {
        if (a[x] == b[y]) stk[dp[x][y]] = a[x], x--, y--;
        else {
            if (dp[x - 1][y] > dp[x][y - 1]) x--;
            else y--;
        }
    }
    printf("%s\n", stk + 1);
    return 0;
}