hdu 5791 Two n^2 dp

題解：

dp[i][j]表示A序列前i個數和B序列前j個數的相同子序列對有多少個。複雜度O(n^2)O(n​2​​)

  看了題解就會了。。。。。

ACcode：

#include <bits/stdc++.h>
#define maxn 1000
#define mod 1000000007
#define ll long long
using namespace std;
int a[maxn],b[maxn];
ll dp[maxn][maxn];
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;++i)scanf("%d",&a[i]);
        for(int j=1;j<=m;++j)scanf("%d",&b[j]);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j){
                dp[i][j]=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mod)%mod;
                if(a[i]==b[j])
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1]+1+mod)%mod;
            }
        cout<<dp[n][m]<<'\12';
    }
    return 0;
}