【概率性 dp】A000

概率性 dp】A000"/>

【概率性 dp】A000

一、Problem

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

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

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

请计算「两个盒子中球的颜色数相同」的情况的概率。

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

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

二、Solution

方法一：暴搜

思考

两个盒子中出现「两个盒子中球的颜色数相同」时的概率，又由于球总数一定是偶数，所以问题变为：两盒子的球数相同且颜色数相同时的概率；

模拟放球…

• 定义状态：
  • dfs(i, m1, c1, m2, c2, k)：表示取第 i 中颜色的球时，盒子一有 m1 个球，c1 种颜色； 盒子二有 m2 个球，c2 种颜色时共有 k 种方案的概率
• 思考状态转移方程：
  • 参考代码…

class Solution {
public:long n, s, ans, tot, half;long fac(int n) {return !n ? 1 : fac(n-1)*n;}// 排列数：a!/(a-b)!long A(int a, int b) {return fac(a)/fac(a-b);}// 组合数 C = A/b!long C(int a, int b) {return A(a, b)/fac(b);}void dfs(int i, int m1, int c1, int m2, int c2, long long k, vector<int>& A) {if (m1 > half || m2 > half)return;if (i == n) {tot+=k;if (m1==m2 && c1==c2) ans+=k;return;}for (int j=0; j<=A[i]; j++) {dfs(i+1, m1+j, c1+(j>0), m2+A[i]-j, c2+(j<A[i]), k*C(A[i], j), A);}}double getProbability(vector<int>& A) {n=A.size(), half=accumulate(A.begin(), A.end(), 0)/2;dfs(0, 0, 0, 0, 0, 1, A);return 1.0*ans/tot;}
};

优化：可以提前将 x（x∈[1,n]) 的阶乘算出来

class Solution {
public:long n, s, ans, tot, half;vector<long> fac;vector<long> get_fac(int n) {vector<long> fac(n+1); fac[0]=1;for (int i=1; i<=10; i++) fac[i]= i * fac[i-1];return fac;}// 排列数：a!/(a-b)!long A(int a, int b) {return fac[a]/fac[a-b];}// 组合数 C = A/b!long C(int a, int b) {return A(a, b)/fac[b];}void dfs(int i, int m1, int c1, int m2, int c2, long long k, vector<int>& A) {if (m1 > half || m2 > half)return;if (i == n) {tot+=k;if (m1==m2 && c1==c2) ans+=k;return;}for (int j=0; j<=A[i]; j++) {dfs(i+1, m1+j, c1+(j>0), m2+A[i]-j, c2+(j<A[i]), k*C(A[i], j), A);}}double getProbability(vector<int>& A) {n=A.size(), half=accumulate(A.begin(), A.end(), 0)/2;fac = get_fac(10);dfs(0, 0, 0, 0, 0, 1, A);return 1.0*ans/tot;}
};

复杂度分析

• 时间复杂度： O ( . . . ) O(...) O(...)，
• 空间复杂度： O ( . . . ) O(...) O(...)