最长公共子序列 LCS

📘 题目描述

给定两个字符串 $s,t$，求出它们的最长公共子序列长度。字符串长度 $1\leq |s|,|t|\leq 2000$。

💡 解题思路

🔢 状态定义

• $f_{i,j}$ 表示字符串 $s[1..i]$ 和字符串 $t[1..j]$ 的最长公共子序列长度。

🔁 状态转移

• 如果 $s[i] = t[j]$，则 $f_{i,j} = f_{i-1,j-1} + 1$。
• 否则，$f_{i,j} = max(f_{i-1,j}, f_{i,j-1})$。

综上：

\[ f_{i,j} = \begin{cases} f_{i-1,j-1} + 1, & \text{if } s[i] = t[j] \\ max(f_{i-1,j}, f_{i,j-1}), & \text{otherwise} \end{cases} \]

🟡 初始化：

初始化时，$f_{i,0} = 0$，$f_{0,j} = 0$。

• 含义：当字符串 $s$ 为空时，最长公共子序列长度为 $0$。同理当 $t$ 为空时，最长公共子序列长度为 $0$。

✅ 统计答案

• $ans=f_{n,m}$。

⏱️复杂度分析

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

✅ 代码实现

int n = s.size(), m = t.size();
s = " " + s, t = " " + t;
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        if (s[i] == t[j])
        {
            f[i][j] = f[i - 1][j - 1] + 1;
        }
        else
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    }
}