南京大学考研机试题DP

3. dp 求子序列的个数

https://www.acwing.com/problem/content/description/3716/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>

using namespace std;

const int N = 1e4 + 10 , mod = 1000000007;

int T;
char s[N] , p[N];
int f[N];
int n , m;

/*
   首先求公共子序列问题想到 DP
   写出 F[i][j] 函数的含义：
   s数组中由前i个字符构成的子序列 和P数组中前j个字符构成的子串构成的集合
   // 字串和子序列不同的含义是字串是连续的 , 子序列可以不连续
   
   分析状态转移: 
   1. 包含 s[i] 当且仅当 s[i] = p[j]
   f[i][j] = f[i - 1][j - 1] 从上一个状态转移而来 
   上一个状态是由s中前 i - 1 个字符构成的子序列和 p 中前 j - 1 个字符构成的字串
   2. 不包含 s[i] f[i][j] = f[i - 1][j] 
   
   优化空间 
   发现需要优化 f[i][j] = f[i - 1][j] + f[i - 1][j - 1]
   我们发现 f[i][j] = f[i - 1][j] 从 i - 1 层计算得到
   f[i][j] = f[i - 1][j - 1] 由 i - 1 层计算得到 
   如果我们从小到大枚举 j 那么 第 i - 1层的 f[j - 1] 会被 第 i 层的覆盖
   所以 我们需要从 m - 0 枚举 j (为什么到 0 因为 f[0] 也是一种方案)
   
   优化时间
   分析时间复杂度 o(n ^ 2 * Q) > 1e9 我们依然是两维
   其次我们发现依然 TLE 
   但我们知道 只有当 s[i] = p[j] 的时候才会更新
   所以我们只需要将 s[i] = p[j] 的元素枚举即可
   开一个 vector 存 b 中每一个字母出现的下标 
   第一层枚举 S 的时候只需要 第二层枚举 b[s[i] - 'a'] 也就是 p 和 s 相同的下标就可以了

*/

int main()
{
    cin >> T;
    
    while(T --)
    {
        cin >> s + 1 >> p + 1;
        n = strlen(s + 1);
        m = strlen(p + 1);
        
        memset(f , 0 , sizeof f);
        f[0] = 1;
        
        vector<int> b[26];
        for(int i = m ; i ; i --)
        b[p[i] - 'a'].push_back(i);
        
        for(int i = 1 ; i <= n ; i ++)
            for(auto j : b[s[i] - 'a'])
            {
                if(s[i] == p[j])
                f[j] = (f[j] + f[j - 1]) % mod; 
            }
        
        cout << f[m] << endl;
    }
    
    return 0;   
}