题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5791
题目问a和b有多少个相同的子序列。
dp[i][j]表示A序列前i个数和B序列前j个数的相同子序列对有多少个.
cnt[i][j]表示当a[i] == b[j]时以a[i]结尾的相同子序列个数.
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL; 15 typedef pair <int, int> P; 16 const int N = 1e3 + 5; 17 //dp[i][j]表示a[i]b[j]之前的所有相同的自序列个数 18 //cnt[i][j]表示当a[i] == b[j]时以a[i]结尾的相同子序列个数 19 LL dp[N][N], cnt[N][N]; 20 LL a[N], b[N]; 21 LL mod = 1e9+7; 22 int main() 23 { 24 int n, m; 25 while(~scanf("%d %d", &n, &m)) { 26 for(int i = 1; i <= n; ++i) 27 scanf("%lld", a + i); 28 for(int i = 1; i <= m; ++i) 29 scanf("%lld", b + i); 30 memset(dp, 0, sizeof(dp)); 31 memset(cnt, 0, sizeof(cnt)); 32 for(int i = 1; i <= n; ++i) { 33 for(int j = 1; j <= m; ++j) { 34 if(a[i] == b[j]) 35 cnt[i][j] = (dp[i - 1][j - 1] + 1) % mod; 36 dp[i][j] = ((dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]) % mod + cnt[i][j]) % mod; 37 } 38 } 39 printf("%lld ", (dp[n][m] + mod) % mod); 40 } 41 return 0; 42 }