简介
经一位大佬推荐开始刷google kick start的算法题，遇到一道有趣的算法题，题目属于2017年的practice round的第二题，实际上也是2016年round D problem A，这里先简单介绍下题目：
problem
A and B are the only two candidates competing in a certain election. We know from polls that exactly N voters support A, and exactly M voters support B. We also know that N is greater than M, so A will win.
Voters will show up at the polling place one at a time, in an order chosen uniformly at random from all possible (N + M)! orders. After each voter casts their vote, the polling place worker will update the results and note which candidate (if any) is winning so far. (If the votes are tied, neither candidate is considered to be winning.)
What is the probability that A stays in the lead the entire time — that is, that A will always be winning after every vote?
Input
The input starts with one line containing one integer T, which is the number of test cases. Each test case consists of one line with two integers N and M: the numbers of voters supporting A and B, respectively.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the probability that A will always be winning after every vote.
y will be considered correct if y is within an absolute or relative error of 10-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.
Limits
1 ≤ T ≤ 100.
Small dataset
0 ≤ M < N ≤ 10.
Large dataset
0 ≤ M < N ≤ 2000.
Sample
| 输入 | 输出 |
|---|---|
| 2 | Case #1: 0.333333 |
| 2 1 | Case #2: 1.000000 |
| 1 0 |
In sample case #1, there are 3 voters. Two of them support A — we will call them A1 and A2 — and one of them supports B. They can come to vote in six possible orders: A1 A2 B, A2 A1 B, A1 B A2, A2 B A1, B A1 A2, B A2 A1. Only the first two of those orders guarantee that Candidate A is winning after every vote. (For example, if the order is A1 B A2, then Candidate A is winning after the first vote but tied after the second vote.) So the answer is 2/6 = 0.333333…
In sample case #2, there is only 1 voter, and that voter supports A. There is only one possible order of arrival, and A will be winning after the one and only vote.
简单解释
其实问题很简单，就是给定N个1和M个0，这N+M个数字中的合法排序方式是要求对于该序列，在任意一个位置，已经出现的1的次数一定大于0出现的次数，求合法序列出现的概率，这个问题我一开始用递归的方式来做，没有想到用数学的方式来做，后来上网搜了一下，看到这个问题实际上算是卡特兰数的一个衍生问题，为什么这么说呢，两个原因，第一个是这个问题首先直接来看并不是卡特兰数，因为要求序列出现1的次数要大于0出现的次数，第二个是因为N和M的关系仅仅是N>M，而没有进一步的关系，更不存在卡特兰数中的相等关系，所以这题我们需要做一些小小的变化来做。
解题
问题转化
首先我们需要做的就是把问题转变成为能套上卡特兰数的形式，我们来考虑下对于一个合法序列，第一位是什么，这个问题很简单，肯定是1，否则首先就不成立，那么接下来只需要考虑除去第一位的的合法序列，这里为了方便大家理解我做一个转化，不妨令0为-1，1不做变化，那么这个时候合法序列就是对于合法序列的任意一个位置，前面所有数字之和必须要大于等于0，其实这个时候问题就已经渐渐向卡特兰数的形式靠拢了，没有听说过卡特兰数的同学这个看看这个文章, 所以本质上我们就是在求除去第一位的合法序列的数量。
解决思路
这个我们先不考虑第一位有多少种可能性，这个原因我后面再解释，我们先直接计算有多少种除去第一位有多少种合法序列，这个问题有了卡特兰数的基础就好算了，首先考虑总的序列可能性是$$C_{M}^{(N+M-1)}$$，这个问题比较简单，接下来需要考虑的是怎么计算合法序列的数量呢，不过既然我们都计算了总序列的数量，那么大家也都能猜到下一步要计算啥了（笑），我们接下来计算不合法序列的数量，那么不合法序列的数量是多少呢，我们先这样考虑，在一个不合法序列第一次出现不合法的位置，也就是出现的所有数字的和小于0，这个时候我们对前面所有数字的符号进行翻转，此时整个序列就对应到N个1和M-1个-1，每个不合法序列都会被映射到N+M-1个由1和-1组成的序列中，1的数量为N，-1的数量为M-1，所构成的序列，这个问题其实需要简单证明下：
* 正向：每个不合法序列第一个前缀和为-1的位置反转后，形成的序列不同。
* 反向：每个含N个”1”的序列，第一个前缀和为1的位置反转后，形成的不合法序列不同。
这个其实也不难理解，本质上证明两个映射都是唯一的，所以必然数量是相等的，所以实际上不合法序列的数量就是$$C_{M-1}^{(N+M-1)}$$
结果
上面实际上基本上已经搞定了问题的80%，接下来就是20%，上面我们实际上已经计算完了可能序列的数量，就是$C_{M}^{(N+M-1)}$ - $C_{M-1}^{(N+M-1)}$，但是实际上这个结果有个小问题，因为我们没有考虑排列的问题，因为在问题中实际上是需要考虑排列的问题的，因为每个投票的个体是不相同的，所以上面的结果还需要乘以N！* M！，这里其实就能看出来为什么我们之前没有考虑第一位有多少种可能性，因为本质上卡特兰数是不考虑排列的可能性的，所以如果我们在前面考虑了排列反而导致后面的计算公式实际上就是错误的，所以最终结果也差不多出现了，($C_{M}^{(N+M-1)}$ - $C_{M-1}^{(N+M-1)}$)*N!*M! / (N+M)!，经过化简之后其实就是(N-M)/(N+M)，是不是感觉很神奇，这可能就是数学之美吧～
延伸
这里的延伸主要就是卡特兰数了，这里我不做很多的介绍，网上也有很多博客来介绍的，自己也没有什么特殊的见解就不在这里拾人牙慧了，不过有几个平时比较常见的例子有给定1-n个数字，求合法的出入栈序列；还有求合法的括号序列，也是可以用卡特兰数的思路来解决的；一个稍微不那么直观的例子是，假设已知一个二叉树有n个节点，问有多少种可能的形式，这题其实比较直观的解法是使用递归的方式来求解，不过换个角度来看，可以将遍历二叉树当时添加括号的过程，比如第一次到达一个节点的时候增加一个左括号（，当遍历完这个节点的左子树，再次返回这个节点时就添加一个右括号），此时这个问题就转化为了求合法的括号序列的数量了，这里我不再细说，有兴趣的同学可以去了解了解。
总结
google kick start还是蛮有意思的，不过难度也是不低，值得我们去学习，另外值得推荐一下编程之美这本书，其实卡特兰数在这本书里面是有所介绍的，这本书还介绍了很多其他的数学知识，很有意思，值得大家去看看研究一番。