题目链接

Bobo has a string of length 2(n + m) which consists of characters A and B. The string also has a fascinating property: it can be decomposed into (n + m) subsequences of length 2, and among the (n + m) subsequences n of them are AB while other m of them are BA.
Given n and m, find the number of possible strings modulo (1e9+7)

贪心
先考虑对于一个给定串,是否可以被分成n个AB子序列与m个BA子序列.
从左到右考虑,遇到A,把它标记成AB的A,遇到B把它标记成BA的B,如果标记完了n个AB又遇到了A,那就在这个A前面找一个B和它配成BA,如果找不到,那这个序列就是不合法的.同理,如果标记完了m个BA的B又遇到了B,那就在这个B前面找一个A和它配成AB,如果找不到则不合法.
基于这样的贪心过程,我们也可以判断任意一个前缀是否合法:从左往右标记,前n个A标记为AB的A,之后的A标记为BA的A并向前找配对,如果找不到则不合法.从左往右标记,前m个B标记为BA的B,之后的B标记为AB的B并向前找配对,如果找不到则不合法.

无后效性
任何含有x个A,y个B的合法前缀,它们都是等价的,即如果有一个后缀可以和这些等价前缀中的任一个搭配,那么它也可以和所有这些等价前缀搭配.
合法前缀的定义是满足:至少存在一个以它为前缀的合法串.
分几种情况验证这一事实:
1)x<=n,y<=m
根据贪心方法,一种必然可行的匹配方案是:将A全部标记为AB的A,B全部标记为BA的B,所以前缀内部没有相互配对的,前缀中的字母全部都是和后缀中的字母匹配的,所以对于一个任何一个它的合法后缀而言,我们可以任意调整前缀中A,B的顺序.
2)x>n,y<=m
根据贪心方法,一种必然可行的匹配方案是:前n个A标记为AB的A,所有的B标记为BA的B,并且从第n+1个A开始,每个A都可以和前面的某个B配成BA,一共有x-n个多余的A.如此,这个前缀中有n个A将要同后缀中的B匹配,有y-(x-n)个B要和后缀中的A匹配.所有符合这对(x,y)的合法前缀都可以通过这样的贪心方法和后缀建立同样的关系.
3)x<=n,y>m
这个同上.
4)x>n,y>m
根据贪心方法,一种必然可行的匹配方案是:前n个A标记为AB的A,剩余x-n个A标记为BA的A.前m个B标记未BA的B,剩余y-m个B标记为AB的B.那么前缀中有n-(y-m)个A要和后缀中的B匹配,有m-(x-n)个B要和后缀中的A匹配.这种关系是只和(x,y)这对数量有关系的.

DP
设dp[x][y]为含有x个A,y个B的合法前缀数量.
分几种情况递推:
1)x<=n,y<=m
那么以A结尾的情况有dp[x-1][y]个,以B结尾的情况有dp[x][y-1].
dp[x][y]=dp[x-1][y]+dp[x][y-1]
2)x>n,y<=m
我们考虑此时这个前缀是否可以以A结尾,假如以A结尾,我们先去掉这个A,前面还有x-1个A,y个B,如果存在符合(x-1,y)的前缀的话,那么这之中有y-(x-1-n)个B要和其后的A配对,所以只有y-(x-1-n)>=1即y-(x-n)>=0时才可以以A结尾,并且这时候的前缀并没有变得不合法.若以B结尾,且存在符合(x,y-1)的前缀的话,那么根据贪心过程(x,y)的情况也是合法的.
所以dp[x][y]=dp[x-1][y](y>=x-n)+dp[x][y-1]
3)x<=n,y>m
dp[x][y]=dp[x-1][y]+dp[x][y-1](x>=y-m)
4)x>n,y>m
dp[x][y]=dp[x-1][y](m-(x-1-n)>=1)+dp[x][y](n-(y-1-m)>=1)
dp[x][y]=dp[x-1][y](m+n-x>=0)+dp[x][y](n+m-y>=0)

边界条件:
dp[x][0]=(x<=n)
dp[0][y]=(y<=m)

DP2
上面是填表法DP,下面讨论刷表法DP.
1)x<n,y<m
dp[x+1][y]+=dp[x][y]
dp[x][y+1]+=dp[x][y]
2)x>=n,y<m
此时这个前缀包含的信息是:有n个A将要与后缀中的B配对,有y-(x-n)个B要与后缀中的A配对.故:
dp[x+1][y]+=dp[x][y](y-(x-n)>=1)
dp[x][y+1]+=dp[x][y]
3)x<n,y>=m
此时这个前缀包含的信息是:有m个B将要与后缀中的A配对,有x-(y-m)个A要与后缀中的B配对,故:
dp[x+1][y]+=dp[x][y]
dp[x][y+1]+=dp[x][y](x-(y-m)>=1)
4)x>=n,y>=m
dp[x+1][y]+=dp[x][y](m-(x-n)>=1)
dp[x][y+1]+=dp[x][y](n-(y-m)>=1)