本文转自：http://blog.csdn.net/queuelovestack/article/details/52096337

题意：

给你两个序列A和B

问两个序列有多少个子序列一样

例如{1,2}与{1,2}一样,{1,2,4}与{1,4,2}不一样

题解：

很显然的一道DP题

求的是公共子序列对数

令dp[i][j]表示A序列前i个数和B序列前j个数的相同子序列对有多少个

状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(a[i]==b[j]?dp[i-1][j-1]+1:0)

怎么理解呢?对于序列A,当加入第i个数时,它增加了长度为j的序列B中与该数相同的数,序列B同理

还有增加的取决于a[i]是否等于b[j],若相等,则增加了dp[i-1][j-1]+1对,这个1就是(a[i],b[j])这对,dp[i-1][j-1]则是有共同前缀的对

dp还是要好好理解一下,毕竟还是比较常见,不会很吃亏,本人就是一个很好的例子,总是在dp上吃亏

【时间复杂度&&优化】

O(n^2)

大牛就是大牛，显然就dp了，当我看的时候，看了那么长时间都不知道是dp，我好渣啊 >_< 注意：子序列，模1e9 的一些问题有可能就是dp！

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const ll LINF=0x3f3f3f3f3f3f3f3f;

#define PI(A) cout<<A<<endl

#define SI(N) cin>>N

#define SII(N,M) cin>>N>>M

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

#define dbg(x) cout <<#x<<" = "<<x<<endl

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS= 1e-9 ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN= 1000 + 9 ;

int A[MAXN],B[MAXN];

ll dp[MAXN][MAXN];

int n,m;

int MOD= 1000000007;

int main()

{

    while(SII(n,m))

    {

        //写DP数组尽量从1开始，因为dp的话一般会用到上个状态，为了不让数组越界，所以从1开始

        Rep(i,1,n) SI(A[i]);

        Rep(i,1,m) SI(B[i]);

        Rep(i,1,n)

        Rep(j,1,m)

        {

            dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+(A[i]==B[j]?dp[i-1][j-1]+1:0);

            dp[i][j]%=MOD;

        }

        //一定要注意 有减法的取模时一定要判断答案的正负，如果是负的就+MOD

        PI((dp[n][m]>0?dp[n][m]:dp[n][m]+MOD));

    }

    return 0;

}