（expectation DP）的核心是 expectatioin DP

1^{st} 什么是期望

感觉是一件相对难以理解的概念（

假定存在一个随机试验X，其中共有n种互斥的事件可能发生，而第i个事件出现的概率为P_i，对应的收益为X_i，那么该随机试验的期望值可表示为E(X)=\sum P_iX_i。

是不是觉得有些难以理解呢？

其实我们只需要将其视为一种加权平均数即可

2^{ed} 期望的一些性质

1. E(X+Y)=E(X)+E(Y)

推导过程如下：

左式=\sum_{i,j}(X_i+Y_i)P_iQ_j(P_i,Q_i分别为X和Y第i个事件发生的概率)

=\sum_{i,j}X_iP_iQ_j+\sum_{i,j}Y_iP_iQ_j+

=\sum_iX_iP_i\sum_jQ_j +\sum_jY_jQ_j\sum_iP_i

在此处，\sum_jQ_j、\sum_iP_i均等于1，这一点可以通过概率的基本性质加以理解。

=\sum_iX_iP_i +\sum_jY_jQ_j

=E(X) + E(Y)

2.E(XY)=E(x)E(Y)

推导过程如下：

左式=\sum_{i,j}X_iY_iP_iQ_i

=\sum_{i}X_iP_i \sum_{j}Y_jQ_j

$=E(X)E(