T2-3 潜藏的指令

题意理解

给定字符串 $S$ 和 $T$，求 $T$ 在 $S$ 中作为子序列出现的次数。

子序列：从 $S$ 中选取若干字符，保持相对顺序不变，组成 $T$。

---

思路分析

使用动态规划。

设 $dp[i][j]$ 表示：在 $S$ 的前 $i$ 个字符中，组成 $T$ 的前 $j$ 个字符的方案数。

状态转移：

• 若 $S[i-1] \neq T[j-1]$：当前字符无法匹配

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

• 若 $S[i-1] = T[j-1]$：可以选择用或不用当前字符

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

边界条件：

• $dp[i][0] = 1$：空串是任何串的子序列，方案数为 1

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

---

参考代码

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

const int MOD = 1e9 + 7;  // 模数
const int MAXN = 1005;    // 最大字符串长度

char S[MAXN], T[MAXN];       // S为信号串，T为指令串
long long dp[MAXN][MAXN];    // dp[i][j]表示S前i个字符中组成T前j个字符的方案数

int main() {
    cin >> S >> T;  // 读入两个字符串
    
    int n = strlen(S), m = strlen(T);  // 获取两个字符串的长度
    
    for (int i = 0; i <= n; i++) {  // 边界初始化
        dp[i][0] = 1;  // 空串是任何串的子序列，方案数为1
    }
    
    for (int i = 1; i <= n; i++) {  // 枚举S的前i个字符
        for (int j = 1; j <= m; j++) {  // 枚举T的前j个字符
            dp[i][j] = dp[i - 1][j];  // 不用S[i-1]匹配
            if (S[i - 1] == T[j - 1]) {  // 如果当前字符相同
                dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;  // 加上用S[i-1]匹配的方案数
            }
        }
    }
    
    cout << dp[n][m] << endl;  // 输出答案
    return 0;
}