概率DP学习笔记

# 概率DP学习笔记 --- 前置知识为高中基本数学知识，在此不讲。 ## 知识 1. 条件概率 即使学过，但它很重要。 $P(A|B) = \frac{P(A\ \bigcap B)}{P(B)}$ 2. 全概率公式 其实就是乱搞了搞。 设事件$B1,B2,B3..Bn$是一个完备事件组(事件两两互斥且所有事件交集为全集，这些事件也被称作样本空间的划分)，则对于任意一个事件A，有如下公式成立： $P(A) = P(A|B1)P(B1) + P(A|B2)P(B2) + ... + P(A|Bn)P(Bn);$ 其实就是换了一种方式。 3. 数学期望 通俗来说就是随机变量取值和概率的乘积之和。 性质 ： 数学期望是线性函数，满足$E(aX + bY) = a * E(X) + b * E(Y)$。 此性质具重要，是期望可以线性递推的依据。 4. 贝叶斯公式 * 简单版 ： $P(A)\times P(B|A) = P(B) \times P(A|B)$ 一般推到： $P(A|B) = \frac{P(B|A) \times P(A)}{P(B)}$ * 真 * 贝叶斯公式 $P(Ai|B) = \frac{P(B|Ai)P(Ai)}{\sum_{j=1}^{n} P(Aj|B)P(B)}$ 其实就是个全概率公式套贝叶斯公式。 5. 概率DP 通俗点感性理解就是用DP思想去解决概率问题，一般通常用递推解决。 比较恶心人的地方是感觉很绕，令人难以理解。 建议在题里慢慢感受它的~~奇妙~~毒瘤。 --- ## 收集邮票 [题目链接](https://www.luogu.com.cn/problem/P4550) ### 题目 有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。 现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。 ### 分析 一道令人云里雾里的题。 提醒：千万不要走进一直买买买却一直收集不够的误区，这样会 mengbi 的。 可以先算出期望张数。 设$f[i]$为现在已经取了i张邮票，把剩下的邮票取走的期望次数。 显然$f[n] = 0$, 现在已经取得i张邮票，所以下一次有 $\frac{i}{n}$ 的概率选到已经选的，显然有 $\frac{n-i}{n}$ 的概率选到没选的。 那么转移方程为： $f[i] = \frac{i}{n}(f[i] + 1) + \frac{n-i}{n}(f[i+1]+1)$, 化简一下可得 ： $f[i] = f[i+1] + \frac{n}{n-i}$ 显然这是一个自己转移自己的方程，本来没有什么头绪，但是却通过数学中的移项却消掉了它，虽然感性理解很难，但是事实就是这样，小编也很奇怪。 恩，似乎推出了一个柿子，但是与题目的要求没有啥关系，没关系，我们可以再设$g[i]$表示已经买了i张邮票，把剩下的邮票买走的期望钱数。 我们试着套上面的柿子，那么$g[n] = 0$, 下一次有 $\frac{i}{n}$ 的概率买到已经买的，显然有 $\frac{n-i}{n}$ 的概率买到没买的。 所以转移方程为: $$g[i] = \frac{i}{n}(g[i] + f[i] + 1) + \frac{n-i}{n}(g[i+1] + f[i+1] + 1)$$ 化简得： $g[i] = \frac{i}{n-i} \times f[i] + g[i+1] + f[i+1] + \frac{n}{n-i}$ $f[i]+1$ 表示这次的费用，同理$f[i+1] + 1$也是，因为费用与次数有关系。 这个柿子显然也是自己转移自己，其实比较难理解。 感觉做概率DP就是有种 $不理解——理解——又不理解——又理解$ 一遍遍的逐渐深入的过程。 也希望都能理解吧。 可能这道题有点过于难了。（望谅解） 代码很简单，就不放了。