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

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

做题结果

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

方法：数学+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); } } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。