360的抽奖

抽奖箱内现有m+n张奖票，m张中奖的，n张不中奖的，现在a和b两个人来轮流抽奖，a抽一张b抽一张，谁先抽到有奖的谁赢。由于b是a的爸爸，b暴打了a一顿之后迫使a答应了b一个特权，b每次抽完一张之后可以再抽一张，但是第二次抽出来的这张直接丢弃，不算b的结果。问：输入m和n，在a先抽的情况下求a获胜的概率(抽奖全程不放回)

示例：

输入
1 3
输出
0.5

输入
2 3
输出
0.6

这道题我使用记忆数组+动态规划的方式。 维护一个二维数组arr，纵向为中奖票数，横向为未中奖票数, 那么arr[i][j]的位置的值就是a获胜的概率
我们先初始化这个数组

	0	1	2	3
0	0	0	0	0
1	1	0	0	0
2	1	0	0	0
3	1	0	0	0

箱子里没有一张中奖票时，a获胜概率自然就是0，当箱子里全是中奖票时，a获胜概率自然就是1

这道题的动态规划思路如下：对于每一轮抽奖， a其实有就只有两个可能性，要么在这一步就抽到了奖票，要么没抽到。

当a没抽到奖票时并不代表a输了，只要b这个时候第一张抽到的不是奖票，那么a自然又获得了一次抽奖机会

所以对于arr[i][j]处的概率，无非就是这一次就抽到奖的概率，加上b没有抽到的概率乘以a再次获得抽奖机会后抽到奖的概率。很明显之后的计算结果依赖于之前的计算结果，是一个动态规划的过程

举个例子：
当m=1，n=3，我们设为（1,3）,假设我们已经算出了（1,1）和（1,2）,那么表如下

	0	1	2	3
0	0	0	0	0
1	1	1/2	1/3	0
2	1	0	0	0
3	1	0	0	0

此时奖池的状态是（1，3）

首先a一上来就中奖的概率是1/4，没中奖的概率是3/4。

如果a没中奖，很明显a抽走了一张没中奖的奖票，所以b来抽奖的时候，奖池的状态是（1,2）。b需要抽两张，要想b不中奖，这个时候就分为两种情况

• b抽的两张都没有奖，概率是：(2/3) * (1/2) = 1/3，抽完之后奖池状态是（1， 0）
• b先抽了一张没奖的，又抽了一张有奖的，概率是(2/3) * (1/2) = 1/3，抽完之后奖池的状态是（0， 1）

b抽完之后，a再次获得抽奖机会，这个时候奖池的两种可能状态如上。那么就可以再次查表，查找这两个奖池状态下a的获胜概率即可

综上所述，可求得答案：1/4 + 3/4 * 1/3 * 1 + 3/4 * 1/3 * 0 = 1/2

于是更新数组arr[1][3]处的结果为1/2

	0	1	2	3
0	0	0	0	0
1	1	1/2	1/3	1/2
2	1	0	0	0
3	1	0	0	0

代码如下：

function so(a, b){
    let arr = []
    for(let i = 0; i <= a; i++){
        arr[i] = new Array(b + 1)
        for(let j = 0; j <= b; j++){
            if(j === 0 && i !== 0) arr[i][j] = 1
            else{
                arr[i][j] = 0
            }
        }
    }
    for(let i = 1; i <= a; i++){
        for(let j = 1; j <= b; j++){
            let p1 = (j > 2) ? (((j - 1)/(i + j - 1)) * ((j - 1 - 1)/(i + j - 2))) : 0
            let p2 = (i > 1 && j > 1) ? (((j - 1)/(i + j - 1)) * ((i)/(i + j - 2))) : 0
            arr[i][j] = (i / (i + j)) +
            (j/(i + j)) * p1 * arr[i][(j - 3) >= 0 ? (j - 3) : 0] +
            (j/(i + j)) * p2 * arr[i - 1][(j - 2) > 0 ? (j - 2) : 0]
        }
    }
    return arr[a][b]
}