引入

举一个求期望最简单的例子：

假设有个人在 1号节点处，每一分钟他会缘着边随机走到一个节点或者在原地停留，问他走到4号节点需要平均几分钟？

这是个简单的期望问题，我们用 Ei(i=1,2,3,4) 表示从i号节点走到4号节点的数学期望值。根据题意对1号节点有

$E1=\frac{1}{3}∗(E1+1)+\frac{1}{3}∗(E2+1)+\frac{1}{3}∗(E3+1)$ ①

表示他下一分钟可以走到2或者3或在原地1，每个可能概率是1/3 ,注意是下一分钟，故要加上1。

同理我们对节点2，3同样可以列出

$E2=\frac{1}{3}∗(E1+1)+\frac{1}{3}∗(E2+1)+\frac{1}{3}∗(E4+1)$ ②

$E3=\frac{1}{3}∗(E1+1)+\frac{1}{3}∗(E3+1)+\frac{1}{3}∗(E4+1)$ ③

因为E4=0，这样上面1234式其实就是组成了一组方程组，解方程组就可得出E1，用高斯消元，复杂度是$O(n^3)$。

从上述例子，我们可总结出如何解决期望类问题，根据题意，表示出各个状态的期望（上例的Ei(i=1,2,3,4)），根据概率公式，列出期望之间的方程，解方程即可。

当我们把各个状态当成是一个个节点时，概率关系为有向边，我们可看到，可递推的问题其实就是这个关系图是无环的！那必须要用方程组解决的问题其实就是存在环！ 而且还要指出的是用高斯消元的时候，要注意误差的问题，最好把式子适当的增大，避免解小数，否则误差太大，估计也会卡题。

题目

LightOj1027

题意：

有n扇门，正数的门可以$x_i$时间把人带到终点，负数的门可以$x_i$时间把人带回起点，问到终点的时间的期望为多少。

思路：

设期望为E。

比如样例3 -6 -9，是这样求期望的$E=\frac{1}{3}*3+\frac{1}{3}*(6+E)+\frac{1}{3}*(9+E)$，解一下方程就可以了。解释一下这个$(6+E)$是为什么，因为被带回到起点，就相当于重新开始选择，所以时间就是$(6+E)$。

牛客小白赛8G

题意：

微信抢红包，有一个红包可以被m个人领取，而且红包的总金额是n。如果为第k个抢红包的人时候,所抢到红包金额的期望是多少？（红包的大小在$[0,\frac{2n}{m}]$中均匀随机,特别的当红包的大小小于$\frac{2n}{m}$时,最后剩下的金额会被包入最后一个红包中）。

思路：

$dp[i][j][k]$：剩余i元，还有j个红包，在第k个抢到的期望。

有转移：

$dp[i][j][k]=\int_0^{\frac{2n}{m}}\frac{m}{2n}dp[i-x][j-1][k-1]dx$。

手推：

k=2。

k=1的时候好算，为$\frac{n}{m}$。

k=2：

$\int_0^{\frac{2n}{m}}\frac{m}{2n}\int_0^{\frac{2(n-x_1)}{m-1}}\frac{m-1}{2(n-x_1)}x_2dx_2dx_1=\frac{n}{m}$。

即$E_2=p*E_1$。

因为与k无关，之后的过程是一样的，所以答案为$\frac{n}{m}$。

POJ2096

题意：

有A物品数量为a，B物品数量为b，一个人每天可以得到一个A物品和一个B物品，问得到所有物品的天数期望是多少。

思路：

$E(i,j)$：已经得到了i个A物品和j个B物品要得到所有物品的天数期望。

E(n,s)=0，要求E(0,0)。

有四种情况的转移：没发现任何新的bug和子组件；发现一个新的bug；发现一个新的子组件；同时发现一个新的bug和子组件。

可以列出式子：

$E(i,j)=\frac{ij}{ns}E(i,j)+\frac{(n-i)j}{ns}E(i+1,j)+\frac{i(s-j)}{ns}E(i,j+1)+\frac{(n-i)(s-j)}{ns}E(i+1,j+1)$。

把E(i,j)移项到左边，就可以得到E(i,j)的表达式。

然后递推一下就可以了。