【题目描述】
有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串，请问有多少种方案可以使得这个新串与字符串B相等？注意：子串取出的位置不同也认为是不同的方案。
【输入描述】
第一行是三个正整数n，m，k，分别表示字符串A的长度，字符串B的长度，以及问题描述中所提到的k，每两个整数之间用一个空格隔开。
第二行包含一个长度为n的字符串，表示字符串A。 第三行包含一个长度为m的字符串，表示字符串B。
【输出描述】
输出共一行，包含一个整数，表示所求方案数。由于答案可能很大，所以这里要求输出答案对1,000,000,007取模的结果。
【样例输入】
样例1：
6 3 1
aabaab
aab
样例2：
6 3 2
aabaab
aab
样例3：
6 3 3
aabaab
aab
【样例输出】
样例1：
2
样例2：
7
样例3：
7
【数据范围及提示】
1 ≤ n ≤ 1000，1 ≤ m ≤ 200，1 ≤ k ≤ m。
蒟蒻的70分普通解法：
源代码： #include<cstdio> #include<algorithm> #define INF 1000000007 using namespace std; int m,n,k,f[1001][201][201][2]; char s1[1001],s2[201]; int main() { scanf("%d%d%d%s%s",&n,&m,&k,s1,s2); for (int a=0;a<=n;a++) //边界处理。 f[a][0][0][0]=1; for (int a=1;a<=n;a++) for (int b=1;b<=m;b++) if (s1[a-1]==s2[b-1]) for (int c=1;c<=min(k,b);c++) //注意循环结束条件。 { f[a][b][c][1]=(f[a-1][b-1][c-1][0]+f[a-1][b-1][c][1])%INF; f[a][b][c][0]=(f[a-1][b][c][0]+f[a][b][c][1])%INF; } else for (int c=1;c<=min(k,b);c++) f[a][b][c][0]=f[a-1][b][c][0]; printf("%d",f[n][m][k][0]); return 0; } /* 此题只应天上有，人间能得几回闻。 ——某犇 确实是一道好题，增加了我对DP的恐惧感。 基本思想：（代码中以位置从0开始为准） 设f[a][b][c][1]表示：A串1-a，B串1-b，使用了c个子串，且选用A[a]的方案总数； 设f[a][b][c][0]表示：A串1-a，B串1-b，使用了c个子串，包含选用和不选用A[a]的方案总数； 由此可推得： f[a][b][c][0] = f[a][b][c][1]+f[a-1][b][c][0]； f[a][b][c][1] = f[a-1][b-1][c-1][0]+f[a-1][b-1][c][1]，(A[a]=B[b]) = 0，(A[a]≠B[b])； */
滚动数组优化正解：
源代码： #include<cstdio> #include<algorithm> #define INF 1000000007 using namespace std; int m,n,k,f[201][201][2]={0}; char s1[1001],s2[201]; int main() { scanf("%d%d%d%s%s",&n,&m,&k,s1,s2); f[0][0][0]=1; for (int a=1;a<=n;a++) for (int b=m;b>0;b--) if (s1[a-1]==s2[b-1]) for (int c=1;c<=min(k,b);c++) { f[b][c][1]=(f[b-1][c-1][0]+f[b-1][c][1])%INF; f[b][c][0]=(f[b][c][1]+f[b][c][0])%INF; } else for (int c=1;c<=min(k,b);c++) //某犇使用了memset()。 f[b][c][1]=0; printf("%d",f[m][k][0]); return 0; }