2019牛客暑期多校训练营（第一场）-E（DP）

题目链接：https://ac.nowcoder.com/acm/contest/881/E

题意：求可分解成n个AB和m个BA的字符串的个数。

思路：

　　首先根据贪心思想，前n个A可作为AB的A，后m个A作为BA的A。可以证明，如果将前n个A中的一个作为BA的A，那一定可以从后面找到一个A来替代这个A。同理，前m个B作为BA的B，后n个B作为AB的B。

　　如果不满足上面条件，一定不能满足n个AB和m个BA的要求。

　　那么可以用dp来做，用dp[i][j]表示有i个A和j个B的前缀方案数。根据下一个选A还是选B可以得到dp[i+1][j]和dp[i][j+1]，根据前面的条件有：

　　如果i+1<=n，一定符合条件，直接转移，dp[i+1][j]=dp[i+1][j]+dp[i][j]。同理，如果j+1<=m，dp[i][j+1]=dp[i][j+1]+dp[i][j]。

　　如果i+1>n，那么需要j>=i+1-n，dp[i+1][j]=dp[i+1][j]+dp[i][j]。同理，如果j+1>m，需要i>=j+1-m，dp[i][j+1]=dp[i][j+1]+dp[i][j]。

　　这样合并即可，就得到了转移方程。

AC代码：

#include<cstdio>
using namespace std;

const int MOD=1e9+7;
const int maxn=1005;
int dp[maxn<<1][maxn<<1];
int n,m;

int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<=n+m;++i)
            for(int j=0;j<=n+m;++j)
                dp[i][j]=0;
        dp[0][0]=1;
        for(int i=0;i<=n+m;++i)
            for(int j=0;j<=n+m;++j){
                if(j>=i+1-n)
                    dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
                if(i>=j+1-m)
                    dp[i][j+1]=(dp[i][j+1]+dp[i][j])%MOD;
            }
        printf("%d
",dp[n+m][n+m]);
    }
    return 0;
}