我们可以先得出以下代码

第一个：当前到a字符串第i个

第二个：当前到b字符串第j个

第三个：当前长度到o

第四个：选不选

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long dp[1010][210][210][2],n,m,k;
string a,b;
int main(){
	cin>>n>>m>>k>>a>>b;
	dp[0][0][0][0]=1;
	for(int i=1;i<=n;i++){
		dp[i][0][0][0]=1;
		for(int j=1;j<=m;j++){
			for(int o=0;o<=k;o++){
				if(o!=0){
					if(a[i-1]==b[j-1]){
				    	dp[i][j][o][1]+=dp[i-1][j-1][o][1];
				    	dp[i][j][o][1]+=dp[i-1][j-1][o-1][0];
				    	dp[i][j][o][1]+=dp[i-1][j-1][o-1][1];
				    	dp[i][j][o][1]%=mod;
				    }
				}
                dp[i][j][o][0]+=dp[i-1][j][o][0];
				dp[i][j][o][0]+=dp[i-1][j][o][1];
				dp[i][j][o][0]%=mod;
			}
		}
	}
//	for(int i=0;i<=n;i++)
//		for(int j=0;j<=m;j++)
//			for(int o=0;o<=k;o++){
//				cout<<"		"<<i<<"  "<<j<<"  "<<o<<"  0  "<<dp[i][j][o][0]<<endl;
//				if(a[i-1]==b[j-1])cout<<"		"<<i<<"  "<<j<<"  "<<o<<"  1  "<<dp[i][j][o][1]<<endl;
//			}
//				
//	
//	cout<<"\n\n\n\n\n\n\n";
	cout<<(dp[n][m][k][0]+dp[n][m][k][1])%mod;
}

然后

10 Wrong Answer(MLE)

果断滚动

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long dp[2][210][210][2],n,m,k;
string a,b;
int main(){
	cin>>n>>m>>k>>a>>b;
	dp[0][0][0][0]=dp[1][0][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int o=0;o<=k;o++){
				dp[i%2][j][o][0]=dp[i%2][j][o][1]=0;
				if(o!=0){
					if(a[i-1]==b[j-1]){
						dp[i%2][j][o][1]+=dp[(i-1)%2][j-1][o][1];
						dp[i%2][j][o][1]+=dp[(i-1)%2][j-1][o-1][0];
						dp[i%2][j][o][1]+=dp[(i-1)%2][j-1][o-1][1];
						dp[i%2][j][o][1]%=mod;
					}
				}
				dp[i%2][j][o][0]+=dp[(i-1)%2][j][o][0];
				dp[i%2][j][o][0]+=dp[(i-1)%2][j][o][1];
				dp[i%2][j][o][0]%=mod;
			}
		}
	}
	cout<<(dp[n%2][m][k][0]+dp[n%2][m][k][1])%mod;
}

100 Accepted

然后我们发现dp[i][j][o][0]与dp[i][j][o][1]代码极度相似

得到

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
string a,b;
int dp[2][205][205],sum[2][205][205];
int main(){
	cin>>n>>m>>k>>a>>b,a=" "+a,b=" "+b;
	dp[0][0][0]=dp[1][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int p=0;p<=k;p++){
				if(a[i]==b[j])sum[i%2][j][p]=(sum[(i+1)%2][j-1][p]+dp[(i+1)%2][j-1][p-1])%1000000007;
				else sum[i%2][j][p]=0;
				dp[i%2][j][p]=(dp[(i+1)%2][j][p]+sum[i%2][j][p])%1000000007;
			}
	cout<<dp[n%2][m][k]%1000000007;
	return 0;
}