ABBA dp
题意
给出2（N+M）个AB字符，问能构造出N个AB子序列和M个BA子序列组成的2*(n+m)的序列种类有多少
思路
碰到计数构造类的题目，首先要去找到判断合法性的条件，即什么情况下合法，什么情况下非法，剩下的工作无非就是实现问题，要么排列组合，要么DP，要么一起用。本题中，还要考虑构造中的贪心问题，也就是给你一堆AB，你怎么构造？很容易想到肯定是前面的A和最后几个B构造出AB，剩下的B和剩下的A构造出BA，也就是前面几个A是用来构造AB的，前面几个B是用来构造BA的，那么我们就可以得出合法判断条件，前面的A过多，导致AB过多 也就是当前A的数量-B的数量>所需AB的数量即：i-j>n 同理B的判断条件为j-i>m 转移很直白，代码量也很短
强调，构造计数类题目需要找出判断合法的条件！！！
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;
long long dp[maxn][maxn];
const int mod=1e9+7;
long long add(long long x,long long y){
return (x*1ll+y)%mod;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)==2){
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=1;i<=m;i++){
dp[0][i]=1;
}
for(int i=1;i<=n;i++){
dp[i][0]=1;
}
for(int i=1;i<=n+m;i++){
for(int j=1;j<=n+m;j++){
dp[i][j]=add(dp[i-1][j],dp[i][j-1]);
if(i-j>n||j-i>m){
dp[i][j]=0;
}
// else if(i>n&&j-m-(i-1-n)>=1)dp[i][j]=add(dp[i-1][j],dp[i][j-1]);
// else if(i>n&&j<=m)dp[i][j]=0;
// else if(j>m&&i-n-(j-1-m)>=1)dp[i][j]=add(dp[i-1][j],dp[i][j-1]);
}
}
cout<<dp[n+m][n+m]%mod<<endl;
}
return 0;
}