做noip模拟赛 遇到期望DP总是跳 所以来咨询一下关于期望DP的一些问题
给出张 n 个点m 条边的有向无环图,起点为1,终点为n,
每条边都有一个长度,并且从起点出发能够到达所有的点,
所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果该节点有k 条出边,
绿豆蛙可以选择任意一条边离开该点,
并且走向每条边的概率为1/k
现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?
比如上题
E(i)表示从1到i的期望长度
已知u->v有边 且知道了E(u)
请问E(v)是等于E(u)+1/k嘛