题意概括

给定两个字符串（或序列）$S_1$ 和 $S_2$，找到它们的最长公共子序列（Longest Common Subsequence, LCS）的长度。子序列是指从原序列中删除零个或多个元素后，其余元素保持原有相对顺序得到的序列。

数据范围:

• 两个字符串的长度 $N, M$ 均满足 $1 \le N, M \le 1000$。
• 字符串由小写英文字母构成。

基础知识

最长公共子序列 (LCS)

LCS 问题是动态规划的经典应用之一。

1. 状态定义: 我们定义 $dp[i][j]$ 表示第一个字符串 $S_1$ 的前 $i$ 个字符（即子串 $S_1[1 \dots i]$）与第二个字符串 $S_2$ 的前 $j$ 个字符（即子串 $S_2[1 \dots j]$）的最长公共子序列的长度。

2. 状态转移方程: 在计算 $dp[i][j]$ 时，我们主要关注 $S_1$ 的第 $i$ 个字符 $S_1[i]$ 和 $S_2$ 的第 $j$ 个字符 $S_2[j]$：

   • 情况一：$S_1[i] == S_2[j]$ 如果这两个字符相等，那么这个字符必然可以作为 $S_1[1 \dots i]$ 和 $S_2[1 \dots j]$ 的一个公共子序列的末尾元素。因此，LCS 的长度就等于 $S_1[1 \dots i-1]$ 和 $S_2[1 \dots j-1]$ 的 LCS 长度加一。

     $$dp[i][j] = dp[i-1][j-1] + 1$$

   • 情况二：$S_1[i] \ne S_2[j]$ 如果这两个字符不相等，那么它们不可能同时作为 LCS 的末尾元素。此时，LCS 的长度取决于两种情况中的较大者：

     1. $S_1[1 \dots i-1]$ 和 $S_2[1 \dots j]$ 的 LCS 长度（即 $dp[i-1][j]$）。
     2. $S_1[1 \dots i]$ 和 $S_2[1 \dots j-1]$ 的 LCS 长度（即 $dp[i][j-1]$）。
     $$dp[i][j] = \max(dp[i-1][j], dp[i][j-1])$$

3. 初始化: $dp[0][j] = 0$ 且 $dp[i][0] = 0$ 对于所有的 $i, j$ 成立，因为任何字符串与空字符串的 LCS 长度都为 0。

4. 最终答案: 两个完整字符串的 LCS 长度即为 $dp[N][M]$。

复杂度分析:

• 时间复杂度: $O(N \cdot M)$，因为需要填充一个 $N \times M$ 大小的 DP 表。
• 空间复杂度: $O(N \cdot M)$，用于存储 DP 表。

样例

样例 1

• 输入:

  abcde
  ace
  

• 输出:

  3
  

• 说明: 最长公共子序列是 "ace"。

样例 2

• 输入:

  banana
  atana
  

• 输出:

  4
  

• 说明: 最长公共子序列是 "aana"。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1005;

string a, b;
int dp[N][N]; // dp[i][j] 表示 a 的前 i 个字符和 b 的前 j 个字符的 LCS 长度

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> a >> b;

    int n = a.length();
    int m = b.length();

    // 为了方便处理边界，我们将字符串看作 1-indexed
    // dp 数组已默认初始化为 0，满足边界条件

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                // 字符匹配，LCS 长度加一
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 字符不匹配，取两种情况的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << endl;

    return 0;
}