Luogu2679
/*
思路清晰：
1.状态
2.转移方程：哪些状态相互影响/记忆化搜索思想
3.循环顺序
4.优化*/
#include<bits/stdc++.h>using namespace std;typedef long long LL;const int mod=1e9+7;
const int MAXN=1005;
const int MAXM=205;char a[MAXN],b[MAXM];
LL dp[2][MAXM][MAXM][2];
int n,m,num,ans;int main(){scanf("%d%d%d",&n,&m,&num);scanf("%s%s",a+1,b+1);dp[0][0][0][0]=dp[1][0][0][0]=1;//状态最重要for(int i=1;i<=n;i++){int now=i&1;//应该先得一些分再去想优化for(int j=1;j<=m;j++)for(int k=1;k<=num;k++){//根据dp方程反推循环顺序dp[now][j][k][0]=(dp[now^1][j][k][0]+dp[now^1][j][k][1])%mod;if(a[i]==b[j])dp[now][j][k][1]=(dp[now^1][j-1][k-1][0]+dp[now^1][j-1][k-1][1]+dp[now^1][j-1][k][1])%mod;// 单独成串，不相连 单独成串，相连 接上一个串elsedp[now][j][k][1]=0;}}printf("%lld\n",(dp[n&1][m][num][0]+dp[n&1][m][num][1])%mod);
}
