1467. 两个盒子中球的颜色数相同的概率

桌面上有 2n 个颜色不完全相同的球，球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。

注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例的解释部分）。

请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 10^-5 以内，则被视为正确答案

示例 1：

输入：balls = [1,1]
输出：1.00000
解释：球平均分配的方式只有两种：
- 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子
这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。

示例 2：

输入：balls = [2,1,1]
输出：0.66667
解释：球的列表为 [1, 1, 2, 3]
随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ：
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。
这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
概率 = 8/12 = 0.66667

示例 3：

输入：balls = [1,2,1,2]
输出：0.60000
解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
概率 = 108 / 180 = 0.6 。

提示：

• 1 <= balls.length <= 8
• 1 <= balls[i] <= 6
• sum(balls) 是偶数

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

失败，看了别人的思路才想出来

 方法：数学+DFS

 1. 组合数计算可以使用杨辉三角

2. 对于第一组选择一种球的情况，会产生两个方面的影响，一个是种类影响，一个是数量影响

        种类影响：

                如果第一组全选一种球，那么第一组就会比第二组多拿一种，用1表示；

                如果第一组全不选一种球，那么第一组就会比第二组少拿一种，用-1表示；

                如果第一组选一部分这种球，另一组也选一部分这种球，那么两者种类相对没有发生变化

        数量影响：一种球一共有 x 个，第一组选 t 个，那么第二组选的就是 x-t 个，第一组比第二组多选了 t-(x-t)个

3. 综上，又种类最多8种，那么第一组选完球的结果就是-8到8种，索引从0开始，所以变成 0到16，长度17；一共有8种球，每种球最多有6个，那么数量差就是 -48到48，索引从0开始，所以变成0到96，长度97

4.dp转移： 

        dp[index+1][i+typeMove][j+cntMove]+=dp[index][i][j]*time;

        其中time代表从几种里面选几种产生的组合数，也就是这种可能性的加权

        类型转移符合种类影响，全选 typeMove=1,全不选为-1，不全选为0

        数量转移符合数量影响，t-(x-t)

  5. 最终结果 ans=dp[n][8][48]/sum, 其中 sum 代表选完最后一种球后，产生的总可能性的种类数目，索引从0开始，实际8对应0种，48对应数量0

class Solution {
    public double getProbability(int[] balls) {
        int n = balls.length;
        long[][][] dp = new long[n+1][17][97];//种类差 -8 到8，数量差-48到48，初始位置 8,48
        dp[0][8][48]=1;
        int[][] c=  new int[9][9];
        c[0][0]=1;
        for(int i = 1; i < 9; i++){
            c[i][0]=1;
            for(int j = 1;j <=i;j++){
                c[i][j]=c[i-1][j]+c[i-1][j-1];
            }
        }
        for(int i = 0; i < n; i++){
            fill(dp,1,balls[i],i,c[balls[i]][0]);
            for(int j = 1; j < balls[i];j++){
                fill(dp,0,j-(balls[i]-j),i,c[balls[i]][j]);
            }
            fill(dp,-1,-balls[i],i,c[balls[i]][balls[i]]);
        }
 
        long sum = 0;
        for(int i = 0; i < 17; i++){
                sum += dp[n][i][48];
        }
        return  1.0*dp[n][8][48]/sum;
    }
 
    private void fill(long[][][] dp, int typeMove, int cntMove, int index,int time){
        for(int i = 0; i < 17;i++){
            for(int j = 0; j<97;j++){
                if(i+typeMove>=0&&i+typeMove<17&&j+cntMove>=0&&j+cntMove<97&&dp[index][i][j]>0){
                    dp[index+1][i+typeMove][j+cntMove]+=dp[index][i][j]*time;
                    // System.out.println("dp["+(index+1)+"]["+(i+typeMove-8)+"]["+(j+cntMove-48)+"]+=dp["+index+"]["+(i-8)+"]["+(j-48)+"]*"+time);
                }
            }
        }
    }
}