T2-4 公共子序列对

题意理解

给定序列 $S$ 和 $T$，求有多少对子序列 $(s', t')$，使得 $s'$ 是 $S$ 的子序列，$t'$ 是 $T$ 的子序列，且 $s'$ 和 $t'$ 内容完全相同。

注意：不同下标组成的相同内容子序列视为不同。

---

思路分析

使用动态规划。

设 $dp[i][j]$ 表示：$S$ 的前 $i$ 个元素和 $T$ 的前 $j$ 个元素中，内容相同的子序列对数量。

状态转移：

考虑是否选择 $S[i]$ 和 $T[j]$：

• 若 $S[i-1] neq T[j-1]$：无法同时选两者作为结尾

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

  （容斥原理：不选 $S[i]$ 的方案 + 不选 $T[j]$ 的方案 - 重复计算的部分）

• 若 $S[i-1] = T[j-1]$：可以同时选两者作为新的结尾

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

  （相当于上面的式子 + $dp[i-1][j-1]$，正好抵消）

边界条件：

• $dp[i][0] = 1$，$dp[0][j] = 1$：空序列与空序列配对，方案数为 1

答案： $dp[n][m]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;  // 模数
const int MAXN = 2005;    // 最大序列长度

int n, m;                 // S的长度n，T的长度m
int S[MAXN], T[MAXN];     // 序列S和T
long long dp[MAXN][MAXN]; // dp[i][j]表示S前i个和T前j个中相同子序列对的数量

int main() {
    cin >> n >> m;  // 读入两个序列的长度
    
    for (int i = 1; i <= n; i++) {  // 读入序列S
        cin >> S[i];
    }
    for (int i = 1; i <= m; i++) {  // 读入序列T
        cin >> T[i];
    }
    
    for (int i = 0; i <= n; i++) {  // 边界初始化：空序列配对
        dp[i][0] = 1;
    }
    for (int j = 0; j <= m; j++) {  // 边界初始化：空序列配对
        dp[0][j] = 1;
    }
    
    for (int i = 1; i <= n; i++) {  // 枚举S的前i个元素
        for (int j = 1; j <= m; j++) {  // 枚举T的前j个元素
            if (S[i] == T[j]) {  // 当前元素相同，可以同时选作结尾
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            } else {  // 当前元素不同，容斥计算
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
            }
        }
    }
    
    cout << dp[n][m] << endl;  // 输出答案
    return 0;
}