一般情况下，解决概率问题需要顺推，而解决期望问题使用逆推，如果定义的状态转移方程存在后效性问题，还需要用到 高斯消元 来优化。概率 DP 也会结合其他知识进行考察，例如 状态压缩，树上进行 DP 转移等。

例1. 生日问题

假设一年有 $365$ 天， 每个人出生日期是均匀随机的，班里有 $30$ 位同学，问“存在两个学生生日相同”的概率？ $50$ 个同学？

分析：直接计算相同概率，比较困难。采用“补集”思想，可以计算“所有同学生日不同”，根据古典概率计算方法：

$P(n位同学生日不同)=\frac{A_{365}^n}{365^n}$

当 $n=30$ , $P(30位同学生日不同)=\frac{365*364*\dots*336}{365*365*\dots*365} \approx 0.29368$ ,那么“存在两个学生生日相同”的概率就是 $1-0.29368=0.70632\approx 70.6\%$

当 $n=50$, $P(50位同学生日不同)\approx 0.029626$,那么“存在两个学生生日相同”的概率就是 $1-0.029626=0.970374\approx 97.03\%$

例2. P2719 搞笑世界杯

【题意简化】

售票窗口出售 A 类门票和 B 类门票各 $n(n\le 1250)$ 张, 有 $2n$ 个人排在窗口前买票。购买时由工作人员通过掷硬币决定，投到正面的买 A 类票，反面的买 B 类票。 掷硬币出现正反的可能性是一样的。如果一类门票提前卖完，则接下来排队买票的人直接买到另外一类门票而无需掷硬币。请问，排在队尾的两个人同时拿到同一种票的概率是多少？

【分析】

本质上就是 $2n$ 个位置安排 $n$ 个 $A$， $n$个 $B$ , 询问最后两个位置相同的概率。 这是不对的，想想为什么。

解法1：补集的思想，概率定义求概率。

所有基本事件数量，在 2n 个人中，选择 n 个人持有 A 类票，那么一共有 $C_{2n}^{n}$ 种组合。但满足“最末尾两人拿到相同门票”的各种事件概率并不一定相等，不是很好计算。利用补集思想，计算“末尾两人拿到不同门票”的概率。

即 $2(n-1)$ 人排完都没有卖完的概率是 $C_{2n-2}^{n-1}\times \frac{1}{2^{2n-2}}$ , “末尾两人拿到相同门票”和“排到最后两人之前，两类门票都没有被卖空”是对立事件，最后答案就是 $1-C_{2n-2}^{n-1}\times\frac{1}{2^{2n-2}}=1-\frac{(2n-2)(2n-3) \dots (n)}{4(n-1)*4(n-2)*\dots*4*1}$。

参考代码：点击

解法2：使用 dp 递推求概率。

定义 $f_{n,m}$ 表示还剩下 $n$ 张 A 类票、$m$ 张 B 类票，最后两张票相同的概率。

如果 $n\le 1$ 且 $m\le 1$ ,说明不可能存在两张相同的票，$f_{n,m}=0$, 否则 $n=0$ 或 $m=0$ ，说明只剩下一种票了， $f_{n,m}=0$。

状态转移方程：$f_{n,m}=\frac{1}{2}(f_{n-1,m}+f_{n,m-1})$

答案是 $f_{n,n}$.

参考代码：点击

例3.Codeforces 148 D Bag of mice

【题意简化】 袋子里有 $w$ 只白鼠和 $b$ 只黑鼠 ，$A$ 和 $B$ 轮流从袋子里抓，谁先抓到白色谁就赢。$A$ 每次随机抓一只，$B$ 每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则 $B$ 赢。$A$ 先抓，问 $A$ 赢的概率。

【分析】

$f_{w,b}$ 表示袋子中有 $w$ 只白鼠、$b$只黑鼠，$A$ 赢的概率

1. 第一种情况，$A$ 直接抓了白鼠，$A$ 赢，这种情况概率为 ：$\frac{w}{w+b}$

2. 第二种情况：$A$ 抓了黑，然后 $B$ 抓黑，跑出黑的或白的，接着 $A$ 赢

   当 $b>3$ ，跑白： $\frac{b}{w+b} \times \frac{b-1}{w+b-1} \times \frac{w}{w+b-2} \times f_{w-1,b-2}$

   跑黑：$\frac{b}{w+b} \times \frac{b-1}{w+b-1} \times \frac{b-2}{w+b-2} \times f_{w,b-3}$

   当 $b=2$ 时，跑出的只能是白，这时要分开讨论,只能跑白：$\frac{b}{w+b} \times \frac{b-1}{w+b-1} \times \frac{w}{w+b-2} \times f_{w-1,b-2}$

例4. CF768D Jon and Orbs

【题意简化】

一个人要取 $k(1\le k\le 1000)$ 种物品，一天只能取一件物品，但不能确定取到的是什么种类。取走的物品会再次生成。求最少需要在第几天，取到 $k$ 种物品的概率不小于 $\frac{p}{2000}$ ，有 $q(q \le 1000)$ 组询问，每组询问给定这个 $p(p \le 1000)$ 。

【分析】

直接算多少天复杂度会爆炸，可以算出前 $i$ 天取出 $j$ 种物品的概率，第一次大于 $\frac{p}{2000}$ 的天数就是答案，转化为 dp 求概率。

定义 $f_{ij}$ 表示前 $i$ 天取出 $j$ 种物品的概率，得到状态转移方程： $f_{i,j}=f_{i-1,j}*\frac{j}{k}+f_{i-1,j-1}* \frac{k-(j-1)}{k}$

例5. P1769 淘汰赛制/POJ3071 Football

【题意简化】

$2^n(n \le 10)$ 名选手参加淘汰赛, 第 $1$ 位和第 $2$ 位比赛，第 $3$ 位和第 $4$ 位比赛，$\dots$ , 获胜者进入下一轮。已知第 $i$ 名选手与 $j$ 比赛获胜的概率，请你预测一下谁夺冠的概率最大。

例6. A0105. 超级购物

【题意简化】

有 $n(n\le 2000)$ 个人要去买东西，他们取买东西的概率为 $p_i$. 现在已知恰有 $r(0 \le r \le n)$ 个人买了东西，在这种条件下，求每个人去买东西的概率。

例7. P2111 考场奇遇

【题意简化】

一场考试共有 $N(N\le 10000)$ 道判断题，已知每道题目小明回答正确的概率都是 $A\%$ 且题目之间相互独立。小红和小明对自己写的答案，结果是 $S$ (一个长为 $N$ 的 $0-1$ 串，其中 $1$ 表示两人答案一样，$0$ 表示不一样)，需要计算出小红对 $Q$ 题以上的概率。

例8. P5249 加特林轮盘赌

【题意简化】

$n(1\le n\le 10^4)$ 个人围在圆桌周围，依次轮流开枪，中枪的概率是完全相同的 $p(0\le p \le 1)$ ，中枪就离开游戏 ，直到圆桌上只剩下一个人停止。给定 $n$ 和 $p$, 询问第 $k$ 个人最终胜利的概率。

【分析】

由于最初抢指向第 1 个人，最终留下一个人获胜，那么位置不同获胜概率是不同。

定义 $f_{i,j}$ 表示还剩余 $i$ 个人，抢指向第一个人时，第 $j$ 个人获胜的概率。

• 当 $j>1$ 时：(1) 第 $1$ 个人中枪，那么第 $j$ 个人就变为第 $j-1$ 个人，即 $p*f_{i-1,j-1}$ ；(2) 第 $1$ 个人没有中枪，第一个就变为第 $j$ 个人了，此时第 $j$ 个人称为第 $j-1$ 个人, 即 $(1-p)*f_{i,j-1}$

  $f_{i,j}=p*f_{i-1,j-1}+(1-p)*f_{i,j-1}$

• 当 $j=1$ 时，枪指向第 $1$ 个人，$1$ 要胜利，那么不能中枪。开枪后，第 $1$ 个人会变为第 $i$ 个人

  $f_{i,1}=(1-p)*f_{i,i}$

  如果使用高斯消元法，时间复杂度会爆炸，手动消元，只需要求 $f_{i,1}$，代入法消元。(注意 $f_{i-1,j}$ 是已知的)

  $f_{i,1}=(1-p)*f_{i,i}$

  $f_{i,1}=(1-p)*(p*f_{i-1,i-1}+(1-p)*f_{i,i-1})$

  $f_{i,1}=(1-p)*p*f_{i-1,i-1}+(1-p)*(p*f_{i-1,i-2}+(1-p)*f_{i,i-2})$

  $\dots$

  $f_{i,1}=p*((1-p)*f_{i-1,i-1}+(1-p)^2*f_{i-1,i-2}+\dots+(1-p)^{i-1}*f_{i-1,1})+(1-p)^i*f_{i,1}$

  移项得到：

  $f_{i,1}=\frac{p}{1-(1-p)^i}((1-p)*f_{i-1,i-1}+(1-p)^2*f_{i-1,i-2}+ \dots +(1-p)^{i-1}*f_{i-1,1})$

  时间复杂度是 $O(n^2)$ ,可以采用滚动数组优化空间。

---

学习完毕

{{ select(1) }}

• YES
• NO