这题dp，好推，方程也不难列。
就是dp的边界太恶心了，我就弱成这样，搞不清楚边界。
还有，就是像这种，数据范围非常大的，就开一下滚动数组吧！
感觉，被这道题down死了
好吧，可能真是状态不好。。过了一会，从新改了改，嗯，原来的思路是没有错的，就是改的时候，忘把一个地方改过来了（n打成m。。。。。。。。。）
滚动数组我去加一下
滚动数组，一个last，一个now，其实就是一个是当前的i，另一个是i-1，只有满足是从上一个转移过来的才能用滚动数组！
最好先把用全数组的想清楚了，再往滚动数组改，因为难免会有一些细节需要处理，例如这里的f【now】【0】【0】和最初的f【last】【0】【0】
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #define debug(x) cout<<#x<<"="<<x<<endl using namespace std; typedef long long ll; const int mod=1000000007; int f[2][205][205],g[2][205][205]; char a[1005],b[205]; int n,m,k; void MOD(int &x) { if (x>=mod) x-=mod; } int main() { scanf("%d%d%d",&n,&m,&k); scanf("%s%s",a+1,b+1); int last=0,now=1; f[last][0][0]=1; for (int i=1;i<=n;i++) { f[now][0][0]=1; for (int j=1;j<=k;j++) { for (int l=1;l<=m;l++) { f[now][j][l]=f[last][j][l]; g[now][j][l]=0; if (a[i]==b[l]) { g[now][j][l]+=g[last][j][l-1]; MOD(g[now][j][l]); g[now][j][l]+=f[last][j-1][l-1]; MOD(g[now][j][l]); f[now][j][l]+=g[now][j][l]; MOD(f[now][j][l]); } } } swap(now,last); } printf("%d",f[last][k][m]); return 0; }
