题意: 给出n,m , 有 2*(n+m)个字符,可以拆分为 n 个子序列 AB 和 m个子序列BA,有多少种符合的方案字符串
解: 前n个A可以任意放,前 m个B可以任意放,
后m个A要放在 B后,后n个B要放在A后。
dp[i][j] 表示字符串含 i个A和 j个B的方案数。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
int dp[maxn][maxn];
int n,m;
const int mod = 1e9+7;
int main()
{
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=0;i<=n+m;i++){
for(int j=0;j<=n+m;j++){
if(i<n+j)
dp[i+1][j] = (dp[i][j] + dp[i+1][j])%mod;
if(j<m+i)
dp[i][j+1] = (dp[i][j] + dp[i][j+1])%mod;
}
}
printf("%d\n",dp[n+m][n+m]);
}
return 0;
}