DP 状态设计
因为需要满足无后效性原则，因此 DP 考虑的肯定是两段前缀。
设 $f_{i,j,p,0/1}$ 表示从 $A$ 中取前 $i$ 个字符（第 $i$ 个字符选或不选）取 $p$ 段，匹配 $B$ 中前 $j$ 个字符的方案数。
DP 状态转移
-
$A_i=B_j$ 时。
显然，有 $f_{i,j,p,0}=f_{i-1,j,p,0}+f_{i-1,j,p,1}$。
还有：$f_{i,j,p,1}=f_{i-1,j-1,p,0}+f_{i-1,j-1,p-1,0}+f_{i-1,j-1,p-1,1}$。
-
$f_{i-1,j-1,p,0}$：将 $A_i$ 加入至 $A_{i-1}$ 所在子串的末尾。
-
$f_{i-1,j-1,p-1,0/1}$：将 $A_i$ 单独作为一个子串。
-
-
$A_i\ne B_j$ 时。
显然，有 $f_{i,j,p,1}=0$，因为不可能存在这种情况。
有 $f_{i,j,p,0}=f_{i-1,j,p,0}+f_{i-1,j,p,1}$，因为 $A_i$ 选不进去，如果选进去只能在末尾，但是并不成立。
滚动数组优化
我们开的 $f$ 数组实际上会达到 $\mathcal O(nmk)=\mathcal O(8\times10^7)$ 的量级，会 $\text{MLE}$。
因此考虑优化，可以滚动数组滚掉一维。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=1000,M=200,K=200,P=1000000007;
int n,m,k;
char a[N+1],b[M+1];
int f[2][M+1][K+1][2];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d %d %d",&n,&m,&k);
scanf("%s%s",a+1,b+1);
f[0][0][0][0]=f[1][0][0][0]=1;
bool mode=0;
for(int i=1;i<=n;i++){
mode=!mode;
for(int j=1;j<=m;j++){
for(int kk=1;kk<=k;kk++){
if(a[i]==b[j]){
f[mode][j][kk][0]=(f[!mode][j][kk][0]+f[!mode][j][kk][1])%P;
f[mode][j][kk][1]=(1ll*f[!mode][j-1][kk][1]+f[!mode][j-1][kk-1][0]+f[!mode][j-1][kk-1][1])%P;
}else{
f[mode][j][kk][0]=(f[!mode][j][kk][0]+f[!mode][j][kk][1])%P;
f[mode][j][kk][1]=0;
}
}
}
}
printf("%d\n",(f[mode][m][k][0]+f[mode][m][k][1])%P);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
