(线性DP,前缀和) O(nmk)

首先考虑如何DP，然后再考虑如何优化。

状态表示：f[i, j, k] 表示只用 S 的前 i 个字母，选取了 k 段，可以匹配 T 的前 j 个字母的方案数。

状态计算：将 f[i, j, k] 表示的所有方案分成两大类：

1. 不用 S[i]，则方案数是 f[i - 1, j, k]；
2. 使用 S[i]，那么可以按 S[i] 所在的一段一共有多少字母继续分类：
   • 如果有 t 个字母，则方案数是 f[i - t, j - t, k - 1]

所以 f[i, j, k] = f[i - 1, j, k] + sum(f[i - t, j - t, k - 1])。

其中 t 只要满足 S[i - t + 1] == T[j - t + 1] 就可以一直往前枚举，因此最坏情况下的时间复杂度是 O(nm²k)，会超时。

接下来考虑如何优化。

我们发现 f[i, j, k] 第二项的表达式和 f[i - 1, j - 1, k] 第二项的表达式很像，具有递推关系，因此可以令 sum[i, j, k] = sum(f[i - t, j - t, k - 1])，则：

• 如果 S[i] == T[j]，那么 sum[i, j, k] = sum[i - 1, j - 1, k] + f[i - 1, j - 1, k - 1]；
• 如果 S[i] != T[j]，那么 sum[i, j, k] = 0；

至此，时间复杂度可以降至 O(nmk)。

但空间上需要 2nmk 的内存，总共需要 2×1000×2002 个 int，约 305MB，超过了内存限制。

因此需要对空间进行优化。

仔细观察转移方程，发现 f[i, j, k] 和 sum[i, j, k] 均只和第 i - 1 层有关，因此可以使用滚动数组，同时可以发现 j 和 k 只会从更小的值转移过来，因此可以使用类似于 01背包问题优化空间的方式，从大到小枚举 j, k，这样连滚动都可以省略了。

时间复杂度

状态总共有 nmk 个，每个状态需要常数次计算，因此总时间复杂度是 O(nmk)。

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=210,MOD=1e9+7;
int n,m,K;
char a[N],b[N];
int f[M][M],sum[M][M]; 
//状态表示:f[i][j][k] 表示s1的前i个字符中选择k段和构成s2的前j个字符的方案数
//状态计算
// 1.1 不用第i个字符 f[i-1][j][k]
// 1.2用第i个字符 最后长度为t f[i-1][j-1][k-1]+f[i-2][j-2][k-1]+f[i-3][j-3][k-1]....
//   令sum[i][j][k]=f[i-1][j-1][k-1]+f[i-2][j-2][k-1]+f[i-3][j-3][k-1]....
//     sum[i][j][k]=sum(i-1,j-1,k)+f(i-1,j-1,k-1);


int main()
{
    cin>>n>>m>>K;
    cin>>a+1>>b+1;
    f[0][0]=1; //起始方案数
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=1;j--)
        {
            for(int k=1;k<=K;k++)
            {
                if(a[i]!=b[j])
                {
                    sum[j][k]=0;//不相等
                }
                else //递推计算sum[j][k]
                {
                    sum[j][k]=(sum[j-1][k]+f[j-1][k-1])%MOD;
                }
                f[j][k]=(f[j][k]+sum[j][k])%MOD; //计算状态数组
            }
        }
    }
    cout<<f[m][K];
    return 0;
}