一般情况下，解决概率问题需要顺推，而解决期望问题使用逆推，如果定义的状态转移方程存在后效性问题，还需要用到 高斯消元 来优化。概率 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$ 种物品，求一次取一件把所有种类取遍的概率不小于 $\frac{p}{2000}$ 的最小天数。 给定 $p$ , $Q$ 次询问。

例5. P1769 淘汰赛制/POJ3071 Football

例6. UVA11181 条件概率 Probability|Given

【题意简化】

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

例7. P2111 考场奇遇

【题意简化】

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

学习完毕

{{ select(1) }}

• YES
• NO