猛地发现自己概率与期望这一部分还不怎么会
（准确来说，是只会2n硬核枚举）
所以我决定好好学一学
概率与期望
前置知识
数学期望：在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。（来源：百度百科）
全概率公式：公式表示若事件A1，A2，…，An构成一个完备事件组且都有正概率，则对任意一个事件B都有公式成立。
期望的线性性质：有限个随机变量之和的数学期望等于每个随机变量的数学期望之和。比如对于两个随机变量X,Y,E(X+Y)=EX+EY.
全期望知识：类似全概率公式，把所有情况不重复、不遗漏地分成若干类，每类计算数学期望，然后把这些数学期望按照每类的概率加权求和。
（来源：刘汝佳《算法竞赛 入门经典 训练指南》）
以上两种方法，可以帮助我们利用DP来求概率/期望。
例题
我觉得可能通过做题会更好理解一点，（毕竟刚刚开始学的话看上面的前置知识看得怪难受的），那就让我们先做几道例题吧！
洛谷 P4316 绿豆蛙的归宿
题目描述
给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？
说明/提示
对于20%的数据 N<=100
对于40%的数据 N<=1000
对于60%的数据 N<=10000
对于100%的数据 N<=100000，M<=2*N
如果按我以前对概率与期望的理解，我大概会这么做：硬核模拟，然后把每次的长度与它的概率乘起来。（这样的复杂度劣得惊人）
但现在不一样了！我们可以用DP来完成这道题目。
我们设f[i]为从i到n点的期望长度，容易想到f[n]=0，而f[1]则是我们的答案。
我们的状态转移方程就是：f[v]=(f[u]+w)/de[v]
这样我们就可以逆推求值了。
你可能会想到一个问题：为什么我们要逆推，而不是直接顺推呢？
我试了一下，发现顺推是错的。
为什么呢？
我们首先这样从正面考虑：
每次我们走过的一段路径，对答案的贡献就是走这条路的概率乘上这条路的长度。
那么走过一段路径的概率是多少呢？就是这条路径上走每一条边的概率之积。
也就是说，如果我们走了一条边，那么它的概率会对走过这条边的以后的路径都产生一个影响。
因此我们逆推的时候，只用乘上走这条边的概率就可以了（可以理解为记上了它对以后路径概率的影响）
但是如果是顺推的话，我乘上走这条边的概率，那么其实没有对走过以后的路径的概率产生影响，而是对我们走过这条边以前的路径概率产生了影响。
（如果这个实在不能理解的话也可以自己手玩一下）
那么我们只需在拓扑排序的过程中顺便完成转移就可以了，时间复杂度O(n+m)。
1 #include <iostream>
2 #include <cstdio>
3 #include <queue>
4 #define gc cl==cr&&(cr=(cl=bu)+fread(bu,1,1000000,stdin),cl==cr)?EOF:*cl++
5 #define gs (ch<'0'||ch>'9')
6 using namespace std;
7 const int N=1e5+111,M=2e5+111;
8 int n,m,tot;
9 int hd[N],in[N],de[N];
10 double f[N];
11 struct edge {
12 int n,v,w;
13 }e[M];
14 queue<int>q;
15 char bu[1000011],*cr,*cl;
16 void r(int &x)
17 {
18 x=0;int f=1;char ch=gc;
19 while( gs ) {if(ch=='-') f=-1;ch=gc;}
20 while(!gs ) x=x*10+ch-'0',ch=gc;
21 x*=f;
22 }
23 void add(int u,int v,int w)
24 {
25 e[++tot]=(edge){hd[u],v,w};
26 hd[u]=tot;
27 }
28 int main()
29 {
30 r(n),r(m);
31 for(int i=1;i<=m;i++)
32 {
33 int u,v,w;
34 r(u),r(v),r(w);
35 add(v,u,w);
36 de[u]++,in[u]++;
37 }
38 q.push(n);
39 while(!q.empty())
40 {
41 int tt=q.front();q.pop();
42 for(int i=hd[tt];i;i=e[i].n)
43 {
44 int v=e[i].v,w=e[i].w;
45 in[v]--;
46 f[v]+=((double)w+f[tt])/(double)de[v];
47 if(!in[v]) q.push(v);
48 }
49 }
50 printf("%0.2lf",f[1]);
51 return 0;
52 }
View Code
（未完待续...)