题目描述
有两个仅包含小写英文字母的字符串 A 和 B。
现在要从字符串 A 中取出 k 个互不重叠的非空子串，然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 B 相等？
注意：子串取出的位置不同也认为是不同的方案。
第一行是三个正整数 n,m,k分别表示字符串 A 的长度，字符串 B 的长度，以及问题描述中所提到的 k，每两个整数之间用一个空格隔开。
第二行包含一个长度为 n的字符串，表示字符串 A。
第三行包含一个长度为 m的字符串，表示字符串 B。
一个整数，表示所求方案数。
由于答案可能很大，所以这里要求输出答案对1000000007取模的结果。
一道挺不错的dp，首先很容易想到用dp[i][j][k]表示从A串前i个字母选出k段与B串的前j项相同的方案数，显然：
dp[i][0][0]=1；
接下来考虑如何转移，首先，A[i]可以不参与匹配：
dp[i][j][k]+=dp[i-1][j][k];
其次，当(A[i]==B[j])时，我们可以把A[i]和B[j]单独匹配，也就是：
dp[i][j][k]+=dp[i-1][j-1][k-1];
也可以把A[i]强行接在A[i-1]后面，形成一整个串，所以我们还需要知道以A[i-1]结尾的串与B串前j-1位匹配的方案数，显然这个值为：
dp[i-1][j-1][k]-dp[i-2][j-1][k]；
所以我们得到：
dp[i][j][k]+=dp[i-1][j][k];
dp[i][j][k]+=dp[i-1][j-1][k-1]+dp[i-1][j-1][k]-dp[i-2][j-1][k]；（A[i]==B[j]）
算一下时间O（n*m*k）≈4e7，貌似可以接受，但是空间为320MB，考虑到每一层循环都只用到了i，i-1和i-2，所以我们只运用滚动数组需要保留三项即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #define mod 1000000007 7 #define maxn 2005 8 using namespace std; 9 10 int read() 11 { 12 int res=0,x=1; 13 char c=getchar(); 14 while(c<‘0‘||c>‘9‘) 15 { 16 if(c==‘-‘) 17 x=-1; 18 c=getchar(); 19 } 20 while(c>=‘0‘&&c<=‘9‘) 21 { 22 res=res*10+(c-‘0‘); 23 c=getchar(); 24 } 25 return res*x; 26 } 27 28 int n,m,t; 29 long long f[3][205][205]; 30 char a[maxn],b[maxn]; 31 32 int main() 33 { 34 n=read();m=read();t=read(); 35 scanf("%s",a+1);scanf("%s",b+1); 36 for(int i=1;i<=n;i++) 37 { 38 memset(f[i%3],0,sizeof(f[i%3])); 39 f[0][0][0]=f[1][0][0]=f[2][0][0]=1; 40 for(int j=1;j<=m;j++) 41 for(int k=1;k<=min(j,t);k++) 42 { 43 if(a[i]==b[j]) 44 { 45 f[i%3][j][k]=(f[i%3][j][k]+f[(i-1)%3][j-1][k]+f[(i-1)%3][j-1][k-1])%mod; 46 if(i>=2) f[i%3][j][k]=((f[i%3][j][k]-f[(i-2)%3][j-1][k])%mod+mod)%mod; 47 } 48 f[i%3][j][k]=(f[i%3][j][k]+f[(i-1)%3][j][k])%mod; 49 } 50 } 51 printf("%d\n",f[n%3][m][t]); 52 return 0; 53 }
原文：https://www.cnblogs.com/snowy2002/p/11851427.html
