【AcWing 3713】不同的子序列——动态规划（2019年南京大学考研机试题）-526互联

给定一个字符串 $S$ 和一个字符串 $T$，请问共有多少个 $S$ 的不同的子序列等于$T$。

输入格式
第一行包含整数 $Q$，表示共有 $Q$ 组测试数据。
每组数据第一行包含字符串 $S$，第二行包含字符串 $T$ 。

输出格式
每组数据输出一行，一个结果，由于结果可能很大，因此输出其对 $1000000007$ 取模后的值。

数据范围
$1≤Q≤50$
$1≤|S|,|T|≤10^4$
保证 $T$ 中的每个字符都是随机生成的。
字符串中只包含小写字母。

输入样例：

2
aaabbb
ab
njnunju
nju

输出样例：

9
5

解决方案

线性动态规划

本题如果数据量只有$10^3$的话就是一道常规的公共子序列的$DP$题。
常规解法
设$f[i][j]$表示$s[1...i]$中等于$t[1...j]$的子序列个数。对于$s[i]$有两种方案：与$t[j]$比较，或不与$t[j]$比较。
当$s[i]$不与$t[j]$进行比较时，$f[i][j]$从$(i-1,j)$转移过来，$f[i][j]=f[i - 1][j]$.
当$s[i]$与$t[j]$进行比较时，如果$s[i] == t[j]$, $f[i][j]$就要加上在$s[1...i-1]$中等于$t[1...j-1]$的子序列个数，即$$f[i][j]=(f[i][j]+f[i-1][j-1])%MOD$$由于数据量为$10^4$，观察到状态转移方程只用到了$i-1$的状态，因此可以像$01$背包一样用滚动数组优化，注意到要用$f[i-1][j-1]$，因此内层循环需要倒序遍历。

#include<bits/stdc++.h>

const int N = 10010, MOD = 1000000007; 

void solve(){
    std::string s, t;
    std::cin >> s >> t;
    int m = s.length(), n = t.length();
    std::vector<int> f(n + 5, 0);
    s = ' ' + s;
    t = ' ' + t;
    f[0] = 1;
    for(int i = 1; i <= m; i ++ ){
        for(int j = n; j >= 1; j -- ){
            if(s[i] == t[j]) f[j] = (f[j] + f[j - 1]) % MOD;
        }
    }
    std::cout << f[n] << '\n';
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int q;
    std::cin >> q;
    
    while(q -- ){
        solve();
    }
    
    return 0;
}

时间复杂度: $O(nmq)$ 超时
空间复杂度: $O(n)$

题目数据量为$10^4$, 一次最多有$50$组数据，因此最坏情况下时间复杂度为$5 \times 10^9$。必定超时。需要优化。
参考链接：2019南京大学计算机考研复试机试题分享

要观察到两个点：1、只有在$s[i]==t[j]$时状态才发生转移；2、字符串$t$中字符都是随机生成，说明$t[j] == s[i]$的概率为$\frac{1}{26}$。
因此我们可以首先预处理$26$个字母在$t$中出现的位置。在内层循环时，只从相同字符的位置处进行转移。

#pragma GCC optimize(2)

#include<bits/stdc++.h>

const int N = 10010, MOD = 1000000007;

void solve(){
    std::string s, t;
    std::cin >> s >> t;
    int m = s.length(), n = t.length();
    std::vector<int> f(n + 5, 0);
    std::vector<std::vector<int>> pos(26, std::vector<int>(n + 10, 0));
    std::vector<int> cnt(26);
    s = ' ' + s;
    t = ' ' + t;
    f[0] = 1;
    for(int i = 1; i <= n; i ++ ){
        int u = t[i] - 'a';
        cnt[u] ++ ;
        pos[u][cnt[u]] = i;
    }
    for(int i = 1; i <= m; i ++ ){
        int u = s[i] - 'a';
        for(int j = cnt[u]; j; j -- ){
            f[pos[u][j]] = (f[pos[u][j]] + f[pos[u][j] - 1]) % MOD;
        }
    }
    std::cout << f[n] << '\n';
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    int q;
    std::cin >> q;
    
    while(q -- ){
        solve();
    }
    
    return 0;
}

时间复杂度: $O(\frac{nmq}{26})$