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

给定一个字符串 \(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})\)