最长公共子序列方案

📘 题目描述

给定两个字符串 $s,t$，构造任意一组 LCS 方案。字符串长度 $1\leq |s|,|t|\leq 2000$。

💡 解题思路

🔢 状态定义

• $f_{i,j}$ 表示字符串 $s[1..i]$ 和字符串 $t[1..j]$ 的最长公共子序列长度。
• $g_{i,j}$ 记录状态 $i,j$ 的转移来源是什么。
  • 若 $f_{i,j}$ 的最大值由 $f_{i-1,j-1}+1$ 得到，则 $g_{i,j} = 1$。
  • 若 $f_{i,j}$ 的最大值由 $f_{i-1,j}$ 获得，则 $g_{i,j} = 2$。
  • 若 $f_{i,j}$ 的最大值由 $f_{i,j-1}$ 获得，则 $g_{i,j} = 3$。

最后递归回溯输出方案即可。

⏱️复杂度分析

• 时间复杂度：$O(n\cdot m)$。
• 空间复杂度：$O(n\cdot m)$。

✅ 代码实现

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ary = array<int, 2>;
template <typename T>
using vec = vector<T>;
constexpr int N = 3e3 + 5, mod = 998244353;
int f[N][N], g[N][N];
string a, b;
void print(int i, int j)
{
    if (!i || !j) return ;
    if (g[i][j] == 3) 
    {
        print(i - 1, j - 1);
        cout << a[i];
    }
    else if (g[i][j] == 1) print(i - 1, j);
    else print(i, j - 1);
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> a >> b;
    int n = a.size(), m = b.size();
    a = " " + a, b = " " + b;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j])
            {
                if (f[i - 1][j - 1] + 1 > f[i][j])
                {
                    f[i][j] = f[i - 1][j - 1] + 1;
                    g[i][j] = 3;
                }
            }
            else
            {
                if (f[i - 1][j] > f[i][j - 1])
                {
                    f[i][j] = f[i - 1][j];
                    g[i][j] = 1;
                }
                else
                {
                    f[i][j] = f[i][j - 1];
                    g[i][j] = 2;
                }
            }
        }
    }
    print(n, m);

    return 0; 
}