HDOJ 5791 Two

题目链接：HDOJ 5791

看上去就肯定是一个DP的，为什么？

数据量啊，n和m都是1000，那么dp【i】【j】很好定：a串的前i个和b串的前j个的子串匹配值

那么dp【n】【m】为答案咯

接下来就稍微的吐槽一下题解：（水题）好吧

毕竟还是自己弱了，这个状态转移得考虑到容斥原理

dp【i】【j】肯定是与dp【i-1】【j-1】，dp【i】【j-1】和dp【i-1】【j】有关

当a【i】！=b【j】时，

那么匹配数值应该就是以前的，dp【i-1】【j】+dp【i】【j-1】

但是，这两个部分是有公共部分的，想想怎么来的，交集是dp【i-1】【j-1】

当a【i】==b【j】时，

除了不相等的部分，相等的部分也变长了一格，还需要加上dp【i-1】【j-1】+1

所以dp转移有了

还有一点细节：因为出现了减号，要+mod再%mod来把值变成正的，贴个代码：

const int maxn=1050;
int a[maxn],b[maxn],n,m;
__int64 dp[maxn][maxn];
__int64 mod;
int main(){
	mod=1e9+7;
	//freopen("input.txt","r",stdin);	
	while(scanf("%d%d",&n,&m)!=EOF){
		__int64 ans=0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=m;i++) scanf("%d",&b[i]);
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				//dp[i-1][j]
				//dp[i][j-1]
				if (a[i]!=b[j])
					dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
				else
					dp[i][j]=dp[i-1][j]+1+dp[i][j-1];
				dp[i][j]=dp[i][j]%mod;
			}
		//for(int i=1;i<=n;i++)
		//	for(int j=1;j<=m;j++)
		//		printf("%d%c",dp[i][j],j==m?'\n':' ');
		printf("%I64d\n",(dp[n][m]+mod)%mod);
	}
	return 0;
}