http://acm.nyist.net/JudgeOnline/problem.php?pid=336
动态转移方程。。。。。。
首先我们把dp 开成二维的数组,dp[ i ] [ j ] 表示,a 串中以 第 i 个字符结尾,b 串中以第 j 个字符结尾, a 串包含 b 串的组数。
假设 a[ i ] == b [ j ]
1、 如果包含 b 串 的a 串 含有 a [ i ] ,则dp[i][j] = dp[i-1][j-1], 原因是两个串中都以相同的字母结尾,则结尾字母就无所谓整个串了
2、如果包含 b 串的 a 串不含有a [ i ] ,则 dp[i][j] = dp[i-1][j-1], 原因是a 串中包含 b 串的子串 不包含 a [i] ,a [i] 就无所谓 a 的子串了。
3、由上面两种情况可以看到,第一位 都是i - 1, 所以我们每次运算的时候,对于第一维 只需要 上次的结果即可,第一维就不需要保存,但是也要注意不能被覆盖,因为 j > j - 1,
所以我们进行递推的时候应该右后往前,这一点和0-1 背包由二维变一维很相似。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; int dp[100010]; string a,b; int main() { int n,i,j; cin>>n; while(n--) { cin>>a>>b; memset(dp,0,sizeof(dp)); dp[0] = 1; int len_a = a.size(), len_b = b.size(); if(len_a < len_b) cout<<0<<endl; else if(len_a == len_b) { //cout<<"****"<<endl; if(a==b) cout<<1<<endl; else cout<<0<<endl; } else { for(i = 0; i < len_a; i++) for(j = len_b-1; j >= 0; j--) { if(j > i) continue; if(a[i] == b[j]) dp[j+1] = (dp[j+1] + dp[j]) %10003; } cout<<dp[len_b]<<endl; } } return 0; }