Leetcode – 周赛 – 191 – 两个盒子中球的颜色数相同的概率

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

桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ,其中 balls[i] 是颜色为 i 的球的数量。
所有的球都已经 随机打乱顺序 ,前 n 个球放入第一个盒子,后 n 个球放入另一个盒子(请认真阅读示例 2 的解释部分)。
注意:这两个盒子是不同的。例如,两个球颜色分别为 ab,盒子分别为 [](),那么 [a] (b)[b] (a) 这两种分配方式是不同的(请认真阅读示例 1 的解释部分)。
请计算「两个盒子中球的颜色数相同」的情况的概率。

样例

示例 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 。

示例 4:

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

示例 5:

输入:balls = [6,6,6,6,6,6]
输出:0.90327

提示

  • 1 <= balls.length <= 8
  • 1 <= balls[i] <= 6
  • sum(balls) 是偶数
  • 答案与真实值误差在 10^-5 以内,则被视为正确答案

思路

【状态表示】

dp[c][i][p][q] 表示已经放入了 c 种颜色,第一个盒子中有 i 个球, 第一个盒子中有 p 种颜色,第二个盒子中有 q 种颜色的概率。

【初始化】

dp[0][0][0][0] = 1 表示还没有放入任何一种颜色,两个盒子都为空的概率为 1

【状态转移】

状态转移的过程,就是取第 c 个颜色球的过程。

具体方程为 dp[c][i+l][np][nq] += dp[c-1][i][p][q] * v

假设表示第 c 种颜色共有 cnt 个球,其中 l 个放入第一个盒子, cnt - l 放入第二个盒子,那么 npnq 分别在 lcnt - l 不为 0 时加 1

关于本次概率 v 的计算,v = C(n-i, l) * C(n-(sum-i), cnt-l) / tot 。假设一个盒子中还有 x 个空位, 那么在 x 个空位中放入 y 个相同颜色的球的方案数应该是 C(x/y) 。所以对于第一个盒子有 C(n-i, l) ,对于第二个盒子有 C(n-(sum-i), cnt-l) ,其中 sum 是前 c-1 种颜色的数量总和。至于 tot ,显然是枚举 l 计算出来的方案数总和。

代码

double dp[10][30][10][10];
class Solution {
public:
    double C(int n, int m) {
        if(m > n) return 0;
        if(m == n) return 1;
        double ret = 1;
        for(int i=n; i>m; i--) ret *= i;
        for(int i=1; i<=n-m; i++) ret /= i;
        return ret;
    }
    double getProbability(vector<int>& balls) {
        int m = balls.size(), n = 0;
        for(auto b: balls) n += b; n /= 2;

        for(int i=0; i<=m; i++) {
            for(int k=0; k<=n; k++) {
                for(int p=0; p<=m; p++) {
                    for(int q=0; q<=m; q++) {
                        dp[i][k][p][q] = 0;
                    }
                }
            }
        }
        dp[0][0][0][0] = 1.0;

        int sum = 0;
        for(int c=1; c<=m; c++) {
            int cnt = balls[c-1];
            for(int i=0; i<=n; i++) {
                for(int p=0; p<=m; p++) {
                    for(int q=0; q<=m; q++) {
                        double tot = 0;
                        for(int l=0; l<=cnt; l++) {
                            if(i + l <= n && sum - i + (cnt - l) <= n) 
                                tot += C(n-i, l) * C(n - (sum-i), cnt - l);
                        }
                        for(int l=0; l<=cnt; l++) {
                            if(i+l<=n && sum-i+(cnt-l)<=n) {
                                int np = p + (l > 0 ? 1 : 0);
                                int nq = q + ((cnt - l) > 0 ? 1 : 0);
                                double v = C(n-i, l) * C(n-(sum-i), cnt-l) / tot;
                                dp[c][i+l][np][nq] += dp[c-1][i][p][q] * v;

                            }
                        }
                    }
                }
            }
            sum += cnt;
        }

        double ans = 0;
        for(int p=0; p<=m; p++) {
            ans += dp[m][n][p][p];
        }
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇