给定两个字符串 A A 和 B B ，求两个字符串的公共子序列个数。

题解

设 f(i,j) f(i, j) 为 A A 串前 i i 位和 B B 串前 j j 位的公共子序列个数，则

f(i,j)={f(i,j−1)+f(i−1,j)+1Ai=Bjf(i,j−1)+f(i−1,j)−f(i−1,j−1)Ai≠Bj f(i, j) = \begin{cases} f(i, j - 1) + f(i - 1, j) + 1 & A_i = B_j\\ f(i, j - 1) + f(i - 1, j) - f(i - 1, j - 1) & A_i \neq B_j \end{cases}

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
const int MAXN = 1005;
const int MOD = 1000000007;
int a[MAXN + 1], b[MAXN + 1], dp[MAXN + 1][MAXN + 1], n, m;
int main() {
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= m; i++) scanf("%d", &b[i]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (a[i] == b[j]) dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % MOD;
                else dp[i][j] = ( ( (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) ) % MOD + MOD ) % MOD;
            }
        printf("%d\n", dp[n][m] % MOD);
    }
    return 0;
}