也许更好的阅读体验

数学期望

符号

$E=p\ast v$E=p∗v 其中 $E$E为期望， $v$v为权值， $p$p为概率

含义

期望表示多个可能事件的合理分配情况 (本人自己的理解，不喜勿喷)
汉语期望意思是指人们对某样东西的提前勾画出的一种标准，达到了这个标准就是达到了期望值(百度百科)
数学期望也可认为是进行某件事能得到的平均结果，或者理想代价
期望值也许和每个得到值都 不相等
举个例子
你去买彩票，每张彩票 $10$10元，中了奖可以得 $10000$10000元，有 $30\%$30%的概率中奖
我们来算一下买一张彩票的期望利润
首先有 $30\%$30%的概率中奖，根据定义期望得到 $30\%\ast 10000$30%∗10000元
又有 $70\%$70%的概率不中奖，那么我们期望得到 $70\%\ast 0$70%∗0元
我们每次买一张彩票 $100$100会花掉 $10$10元
所以有 $E=30\%\ast 10000+70\%\ast 0-10=290$E=30%∗10000+70%∗0−10=290
我们可认为每买一张彩票赚了 $290$290元
但是实际上无论怎样，一张彩票都不会赚 $290$290元的。

转移方程

几种常见设转移方程数组的方法

1. 设 $f\left[i\right]$f[i]表示的是由 $i$i状态变成 最终 状态的期望
2. 按照题意直接设
3. 把选择的东西加入数组，如 $f\left[i\right]\left[j\right]$f[i][j]表示第 $i$i个物品选 $j$j个的期望或 $f\left[i\right]\left[j\right]$f[i][j]表示有 $i$i个 $A$A物品， $j$j个 $B$B物品的期望

求转移方程
应优先考虑进行操作后当前状态会怎么样，而不是如何变成当前状态，即先考虑 逆向
如果逆向没有思路，则考虑 正向

经典例题

注：没有贴出代码，有些题目现在找不到了 (至少博主没有找到)，也有博主自己想的题目 (很水)，如博主有写代码则已放进标题的链接里，那些链接都是题解，不是原题链接

SP1026FavoriteDice

题目大意

一个 $n$n面的骰子，求期望掷几次能使得每一面都被掷到

解决方法

设 $f\left[i\right]$f[i]表示已经掷到过 $i$i面，还 期望掷多少次骰子使每一面都被掷到
现在掷一次骰子，有两种情况

1. 有 $\frac{i}{n}$ni​的概率掷到已经掷到过的面，此时仍然还要掷 $f\left[i\right]$f[i]次骰子
2. 有 $\frac{n-i}{n}$nn−i​的概率掷到没掷到过的面，此后就掷到过 $i+1$i+1个面了，还需掷 $f[i+1]$f[i+1]次骰子

需要注意的是，无论是掷到以上哪种情况，都需要掷一次骰子
所以有
$f\left[i\right]=\frac{i}{n}f\left[i\right]+\frac{n-i}{n}f[i+1]+1$f[i]=ni​f[i]+nn−i​f[i+1]+1
将其化简
$f\left[i\right]=f[i+1]+\frac{n}{n-i}$f[i]=f[i+1]+n−in​

初值 $f\left[n\right]=0$f[n]=0，答案为 $f\left[0\right]$f[0]
应逆向循环

涂格子/小孩和礼物

题目大意

有 $n$n个格子，每次等概率随机给一个格子染色，问涂 $m$m次后期望有多少格子被染色了

解决方法

设 $f\left[i\right]$f[i]表示涂 $i$i次后期望有多少格子被染色了
现在进行第 $i$i次染色，仍然有两种情况

1. 有 $\frac{f[i-1]}{n}$nf[i−1]​的概率涂到已经涂过的格子
2. 有 $\frac{n-f[i-1]}{n}$nn−f[i−1]​的概率涂到没涂过的格子

需要注意的是，无论是以上哪种，都已经有 $f[i-1]$f[i−1]个格子被染色了
所以有
$f\left[i\right]=\frac{f[i-1]}{n}\cdot 0+\frac{n-f[i-1]}{n}\cdot 1+f[i-1]$f[i]=nf[i−1]​⋅0+nn−f[i−1]​⋅1+f[i−1]
将其化简
$f\left[i\right]=\frac{n-f[i-1]}{n}+f[i-1]=\frac{n-1}{n}f[i-1]+1$f[i]=nn−f[i−1]​+f[i−1]=nn−1​f[i−1]+1
此时该式就是一个等差数列套等比数列
于是我们可以求其通项公式，博主懒得求了写下大致过程

令 $k=\frac{n-1}{n}$k=nn−1​
$f_n=k{f}_{n-1}+1$fn​=kfn−1​+1
$f_n+\frac{1}{k-1}=k{f}_{n-1}+\frac{k}{k-1}$fn​+k−11​=kfn−1​+k−1k​
$f_n+\frac{1}{k-1}=k(f_{n-1}+\frac{1}{k-1})$fn​+k−11​=k(fn−1​+k−11​)
令 $g_n=f_n+\frac{1}{k-1}$gn​=fn​+k−11​
则 $g_n=k{g}_{n-1}$gn​=kgn−1​
怎么求 $g_n$gn​就不用说了吧
$f_n=g_n-\frac{1}{k-1}$fn​=gn​−k−11​
$f_n$fn​也能求出来了

初值 $f\left[0\right]=0\mid f\left[1\right]=1$f[0]=0∣f[1]=1答案为 $f\left[m\right]$f[m]
应正向循环

简单题

题目大意

桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。

解决方法

设 $f\left[i\right]\left[j\right]$f[i][j]表示有 $i$i张红牌， $j$j张黑牌的期望收益
考虑翻一张牌，还是有两种情况

1. 有 $\frac{i}{i+j}$i+ji​的概率翻到红牌，此后就只有 $i-1$i−1张红牌， $j$j张黑牌
2. 有 $\frac{j}{i+j}$i+jj​的概率翻到黑牌，此后就只有 $i$i张红牌， $j-1$j−1张黑牌

需要注意的是，不要忘了翻开的牌的贡献
翻开一张牌后，该颜色牌数目就少了一张

所以有
$f\left[i\right]\left[j\right]=\frac{i}{i+j}\left(f\right[i-1\left]\right[j]+1)+\frac{j}{i+j}\left(f\right[i\left]\right[j-1]-1)$f[i][j]=i+ji​(f[i−1][j]+1)+i+jj​(f[i][j−1]−1)
由于是最优策略，所以咱是不可能赔钱的
$f\left[i\right]\left[j\right]=max(0,\frac{i}{i+j}(f[i-1]\left[j\right]+1)+\frac{j}{i+j}(f\left[i\right][j-1]-1\left)\right)$f[i][j]=max(0,i+ji​(f[i−1][j]+1)+i+jj​(f[i][j−1]−1))

初值 $f\left[0\right]\left[1\right]=0,f\left[1\right]\left[0\right]=1$f[0][1]=0,f[1][0]=1，答案为 $f\left[R\right]\left[B\right]$f[R][B]
应正向循环

亚瑟王

题目大意

给出 $n$n个技能，每个技能按输入顺序有 $p\left[i\right]$p[i]的概率释放并造成 $d\left[i\right]$d[i]的伤害。每轮游戏从前往后顺序查看每个技能，若技能发动过则跳过，没发动过则以 $p\left[i\right]$p[i]的技能发动，即每个技能只能发动一次，若将一个技能发动，则进行下一轮游戏，没有成功发动或被跳过就查看下一个技能，一轮游戏可能每个技能都不发动，问 $r$r轮游戏一共能造成的伤害期望。

解决方法

因为有一个顺序查看的限制，没有后效性的状态是十分不好设的，因为不知道前面有几个技能发动了，若一个技能前面的技能在某轮发动了，则该技能本轮一定不能发动，若前面有些技能发动过，则它们都会被跳过
为了解决这种情况，我们设状态时试着强制限制技能发动（ $nr$nr枚举情况），当然，设的状态仍然要满足 所有 情况都考虑在内
设 $f\left[i\right]\left[j\right]$f[i][j]表示对前 $i$i个技能进行了 $j$j轮游戏发生的 概率
若前 $i$i个技能进行了 $j$j轮游戏
则有 $j$j轮不会考虑第 $i+1$i+1个技能
即有 $r-j$r−j轮游戏选择了 $i$i之后的技能
此时考虑第 $i+1$i+1个技能的情况，分为两种

1. 有 $p[i+1{]}^{r-j}$p[i+1]r−j的概率 $i+1$i+1号技能从未发动
2. 有 $1-p[i+1{]}^{r-j}$1−p[i+1]r−j的概率 $i+1$i+1号技能发动过

需要注意的是，此时 已经 确定前 $i$i个技能进行并 只进行 了 $j$j轮游戏，其概率应该也计算在内
所以有

1. $f[i+1]\left[j\right]+=1-p[i+1{]}^{r-j}f[i\left]\right[j]$f[i+1][j]+=1−p[i+1]r−jf[i][j]
2. $f[i+1][j+1]+=(1-p[i+1{]}^{r-j}\left)f\right[i\left]\right[j]$f[i+1][j+1]+=(1−p[i+1]r−j)f[i][j]

$j+1$j+1要小于等于 $r$r

初值 $f\left[0\right]\left[0\right]=1$f[0][0]=1，答案在中途计算
应正向循环

计算了概率，别忘了求的是期望伤害，在求概率的时候顺便用概率乘以伤害

抽卡

题目大意

$Morning\_Glory$Morning_Glory最近迷上了抽卡，每次抽卡抽到 $6$6星卡的概率为 $p$p。抽卡活动进行 $n$n天，在第 $i$i天要花 $c\left[i\right]$c[i]游戏币进行抽卡。求 $Morning\_Glory$Morning_Glory抽得 $k$k张 $6$6星卡数时的期望游戏币花费。

解决方法

设 $f\left[i\right]\left[j\right]$f[i][j]表示第 $i$i天抽到 $j$j张 $6$6星卡的期望游戏币花费
在第 $i$i天进行抽卡，有两种情况

1. 有 $p$p的概率抽到 $6$6星卡
2. 有 $1-p$1−p的概率没抽到 $6$6星卡

需要注意的是无论是否翻到，都要花费
所以有
$f\left[i\right]\left[j\right]=p\cdot f[i-1][j-1]+(1-p)\cdot f[i-1]\left[j\right]+c\left[i\right]$f[i][j]=p⋅f[i−1][j−1]+(1−p)⋅f[i−1][j]+c[i]

初值 $f\left[0\right]\left[0\right]=1,f\left[0\right]\left[1\right]=0$f[0][0]=1,f[0][1]=0，答案为 $f\left[n\right]\left[k\right]$f[n][k]
应正向循环

收集邮票

[POJ3682]King_Arthur’s_Birthday_Celebration

这两题是一样的类型，只有概率与计算答案要改一下，这里用收集邮票来做例题
题目大意

有 $n$n种邮票，每天等概率的买一张邮票，第 $i$i天购买要花费 $i$i元，求收集 $n$n种邮票的期望花费

解决方法

先设 $f\left[i\right]$f[i]表示买到 $i$i种邮票后，离买到 $n$n种邮票的期望还差天数
和最上面那题一样的处理方法
考虑当前买了 $i$i张邮票，再买一张邮票，有两种情况

1. 有 $\frac{i}{n}$ni​的概率买到重复的邮票，此时仍只买到 $i$i张邮票
2. 有 $\frac{n-i}{n}$nn−i​的概率买到没买过的邮票，此后就已买到 $i+1$i+1张邮票

需要注意的是，无论哪种情况，都过了一天
所以有
$f\left[i\right]=\frac{i}{n}f\left[i\right]+\frac{n-i}{n}f[i+1]+1$f[i]=ni​f[i]+nn−i​f[i+1]+1
将其化简
$f\left[i\right]=f[i+1]+\frac{n}{n-i}$f[i]=f[i+1]+n−in​

初值 $f\left[n\right]=0$f[n]=0，答案为 $f\left[0\right]$f[0]
应逆向循环

当然这只是期望天数，不是期望花费
设 $g\left[i\right]$g[i]表示 拥有(不是买) $i$i种邮票， 买到 $n$n种邮票的期望花费
考虑当前拥有了 $i$i张邮票，买一张邮票，有两种情况

1. 有 $\frac{i}{n}$ni​的概率买到重复的邮票，此时仍只拥有 $i$i种
2. 有 $\frac{n-i}{n}$nn−i​的概率买到没买过的邮票，此后就已拥有 $i+1$i+1张邮票

需要注意的是，无论哪种情况，都买了一张邮票
此时我们不知道每张邮票多少钱
但我们知道每张邮票和过了多少天有关
这次的注意写在前面，我们是认为有了 $i$i张邮票后才开始，所以第一天邮票价格为 $1$1元
为什么这么设？
我们不知道也不好处理出前面买了多少张邮票，再买到一张邮票要多少钱
但是我们知道第一天肯定是只要 $1$1元的，答案为 $g\left[0\right]$g[0]，中间的过程不重要，只需推出最终答案
我们借助初始状态的这条非常有用的性质于是就设出了这样的 $g$g
这样我们可以知道

1. 若买到重复的邮票，我们知道，因为是设当前是第一天，所以原本希望买到的邮票的天数又往后推了一天，所以总价格要多 $f\left[i\right]$f[i]元，还要加上自己的 $1$1元
2. 若买到没买过的邮票，同理，因为后面的 $g[i+1]$g[i+1]也是从第 $1$1天开始考虑的，所以原本希望买到的邮票数也往后推了一天，所以价格要多 $f[i+1]$f[i+1]元，还要加上自己的 $1$1元

所以有

1. $g\left[i\right]+=\frac{i}{n}\left(g\right[i]+f[i]+1)$g[i]+=ni​(g[i]+f[i]+1)
2. $g\left[i\right]+=\frac{n-i}{n}\left(g\right[i+1]+f[i+1]+1)$g[i]+=nn−i​(g[i+1]+f[i+1]+1)

总写下来就是 $g\left[i\right]=\frac{i}{n}\left(g\right[i]+f[i]+1)+\frac{n-i}{n}\left(g\right[i+1]+f[i+1]+1)$g[i]=ni​(g[i]+f[i]+1)+nn−i​(g[i+1]+f[i+1]+1)

将其化简得到
$g\left[i\right]=\frac{i}{n-i}f\left[i\right]+g[i+1]+f[i+1]+\frac{n}{n-i}$g[i]=n−ii​f[i]+g[i+1]+f[i+1]+n−in​

初值 $g\left[n\right]=0$g[n]=0，答案为 $g\left[0\right]$g[0]
应逆向循环

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力