DP总结(五，概率与期望)

嘛，既然是概率与期望 DP，还是得先讲概率与期望的。

0.概率论

概率基本定义

我们先给出以下几个符号：

$\Omega$ 表示样本空间
$A,B$ 等拉丁大写字母表示事件，是样本空间的子集
$P(A)$ 表示事件 $A$ 发生的概率，是一个函数
有时候我们不需要关注那么多的事件，所以会有事件域 $\mathcal{F}$ ，就是一些事件的集合，作为全集

因为事件是样本空间的子集，所以我们可以把集合的运算放到事件上。

在概率论中，我们将 $A \cup B$ 记为 $A + B$ ，将 $A \cap B$ 记为 $A \cdot B = AB$

随机变量：相当于是取每个值都有一定概率的变量，取值可以是有限集，也可以是无限集，分为离散型和连续型。

分布函数：字面意思，表示随机变量是怎么分布的。

期望基本定义

我认为这就是个加权的概率。

对于一个离散性随机变量，它的期望为 $E(x) = \sum x F(x)$ ，即取值乘以取这个值的概率，连续型的也类似，只不过把求和换成了积分，本质还是一样的， $E(x) = \int _ {-\infty} ^ {\infty} x F(x) \text{d}x$ 。

期望是有线性性的，即 $E(aX + b) = E(a)E(x) + E(b)$ 。

好了，基本的讲完了，剩下的就是 DP 了。

1.概率 DP

一般，我们会设 $dp _ {S}$ 表示某种限制发生的概率，这种限制是可以从某些其他限制转移过来的，因此是个子问题，就是个 DP。

比如下面这道例题：

CF148D↗

袋子里有 $w$ 只白鼠和 $b$ 只黑鼠，公主和龙轮流从袋子里抓老鼠。谁先抓到白色老鼠谁就赢，如果袋子里没有老鼠了并且没有谁抓到白色老鼠，那么算龙赢。公主每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。每次抓的老鼠和跑出来的老鼠都是随机的。公主先抓。问公主赢的概率。

我们设 $dp _ {i,j}$ 表示还剩 $i$ 只白鼠， $j$ 只黑鼠，现在该公主抽赢的概率，边界条件是 $dp _ {0,j} = 0,dp _ {i,0} = 1$ 。

接下来就是分类讨论可能发生的所有情况。

公主抓到一只白鼠，公主直接胜利，概率为 $\frac{i}{i + j}$
公主抓到一只黑鼠，龙抓到一只白鼠，龙胜利，概率为 $\frac{j}{i + j} \times \frac{i}{i + j - 1}$
公主抓到一只黑鼠，龙抓到一只黑鼠，跑了一只黑鼠，概率为 $\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2}$ ，注意是从转移 $dp _ {i,j - 3}$
公主抓到一只一只黑鼠，龙抓到一只黑鼠，跑了一只白鼠，概率为 $\frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2}$ ，从转移 $dp _ {i - 1,j - 2}$

考虑对答案的贡献，第二种不计入答案，其他的需要合法，则 $dp _ {i,j} = \frac{i}{i + j} + [j \ge 3] \times \frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{j - 2}{i + j - 2} \times dp _ {i,j - 3} + [i \ge 1 \wedge j \ge 2] \times \frac{j}{i + j} \times \frac{j - 1}{i + j - 1} \times \frac{i}{i + j - 2} \times dp _ {i - 1,j - 2}$

概率 DP 一般是顺推，转移方程一般是大力分类讨论出来的。

2.期望 DP

这个就很难了，裸的期望 DP 一般是倒着推，并且状态是形如“已经……的期望”。

但是，一般不会给你出裸题，可能会从期望的定义入手，让你写一个概率 DP，计入答案时带权，也有可能是等概率的情况，直接让你用等概率情况总数除以情况总数，转成计数 DP~~（虽然我哪个都菜就是了）~~。

不同于其他 DP 的是，概率/期望 DP 要求了你有足够强大的推式子能力，并且能结合一般 DP 和概率论，以及其他各种东西。

先看几道例题：

Ex.1 Luogu P4316↗

我们先按照套路，设 $dp _ u$ 表示已经到达 $u$ ，到终点的期望路径长度。

则 $dp _ u = \sum _ {v \in to(u)} \frac{1}{k _ u} dp _ v + w(u,v)$ 。

这个就要求我们在计算 $u$ 之前计算出 $v$ ，在 DAG 上是什么？拓扑排序！

我们在跑拓扑排序的同时计算 $dp _ u$ 就行了。

Ex.2 校内 2025.3.17 模拟赛 T2

给你一个数列 $A$ ，满足 $A$ 无限长，并且 $A _ i \in [1,m] \cap \Z$ 且等概率随机。求给定长为 $n$ 的序列 $B$ 在 $A$ 中的最小出现位置的期望。

Example In:

Example Out:

1
4

这个乍一看不好做，我们先设 $dp _ {i}$ 表示现在已经满足 $B$ 的前 $i$ 位，出现位置的期望，则 $dp _ {i} = \frac{1}{m} dp _ {i + 1} + \frac{1}{m} \sum dp _ {x}$ ，其中 $x$ 表示 $A$ 的子串中前后缀相等的集合，即 Border 集合。

其实，我们可以通过样例，大胆猜个结论，即答案为 $m ^ n$ ，但是，这个是错的，因为你可以打表发现， $B _ 1 = 2,B _ 2 = 2$ 的答案为 $6$ 。

如果你是打表仙人，你能发现，如果前后缀有相等的，则答案会多一点。结合上面的 Border，我们可以猜出 $Ans = m ^ n + \sum _ {p \in \text{Border}(B)} m ^ p$ ，然后跑个 KMP 就出来了。

详细证明需要强大的观察与推式子能力，我太菜了不会。

这个题告诉我们，期望 DP 可以和几乎所有内容结合。

因此，多看多练吧。

3. 有后效性 DP

有的时候，我们可能推出来一个既跟先前的状态有关，又跟之后的状态有关的方程，放别的题你可能会觉得自己推错了，但这是概率 DP，DP 状态是到达某个状态的概率/期望，我们为什么不用代数方法来解决呢？

我们可以把 DP 方程变换一下，写成一个数学方程的形式，然后就可以用高斯消元法解出每一个 DP 值。

我感觉这个反而是最简单的，因为太套路了。

Thanks for reading!

DP总结(五，概率与期望)

2025 3月 14 周五

1629 字 · 7 分钟

算法学习笔记 OI 动态规划数学概率论