#include<iostream> using namespace std; long long f[201][201]={1},sum[201][201],n,m,ki; char a[1001],b[201]; int main(){ cin>>n>>m>>ki>>a>>b; for(int i=1;i<=n;i++) for(int j=m;j>=1;j--) for(int k=ki;k>=1;k--) f[j][k]=(f[j][k]+ (sum[j][k]= a[i-1]==b[j-1]? sum[j-1][k]+f[j-1][k-1] : 0))%1000000007; cout<<f[m][ki]; }

用sum处理了一下，然后可以滚动掉一维，于是成了2维11行dp A' 表示由串A前i个字符组成的串 B' 表示由串B前j个字符组成的串 设f(i,j,k)为从A'中，顺序取k个不重复子串，首尾相接后与B'相等的方案数

#include <bits/stdc++.h> #define ll long long using namespace std; const int mod = 1000000007; ll dp[201][201]; ll s[201][201]; int main() { dp[0][0] = 1ll; int n, m, k; string a,b; cin >> n >> m >> k >> a >> b; }

DP 设f[i][j[[k][0]表示A的前i个字符匹配B的前j个字符，划分成k段，且当前A串这个字符不取的情况下的方案数。 f[i][j][k][1]则表示A的前i个字符匹配B的前j个字符，划分成k段，且当前A串这个字符取的情况下的方案数。 容易得出，f[i][j][k][0]=f[i−1][j][k][0]+f[i−1][j][k][1]f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1]f[i][j][k][0]=f[i−1][j][k][0]+f[i−1][j][k][1]，即从第i-1个状态直接转移过来。 f[i][j][k][1]=f[i−1][j−1][k−1][0]+f[i−1][j−1][k−1][1]+f[i−1][j−1][k][1](当a[i]=b[j]时)f[i][j][k][1]=f[i-1][j-1][k-1][0]+f[i-1][j-1][k-1][1]+f[i-1][j-1][k][1](当a[i]=b[j]时)f[i][j][k][1]=f[i−1][j−1][k−1][0]+f[i−1][j−1][k−1][1]+f[i−1][j−1][k][1](当a[i]=b[j]时)，分别表示前一个不取当前独成一个子串的情况，前一个取当前独成一个子串的情况和前一个取当前和前一个成同一个子串的情况。 边界f[i][0][0][0]=1f[i][0][0][0]=1f[i][0][0][0]=1。 最后答案为f[n][m][k][0]+f[n][m][k][1]f[n][m][k][0]+f[n][m][k][1]f[n][m][k][0]+f[n][m][k][1]。 四维数组开不下怎么办？观察状态转移方程可以发现，i的状态总是从i-1转移过来，与其他状态无关。故我们滚动第一维即可。 时间复杂度O(nmk)O(nmk)O(nmk)。 AC代码