期望逆推

疑惑了很久，可能有点思路了吧。

举一个常见例子：图上从s开始随机游走，求到t走过的距离期望。
首先思考顺推是否可行。
我们用dp[x]表示由s到x的距离期望。发现这玩意压根没法转移，因为你可以随便拐弯走，最后就会发现有无数次转移到x的情况，即使概率越来越小。也许可以通过转移矩阵的等比求和解决，但实在太麻烦了。

思考逆推，用dp[x]表示由x到t的距离期望。这个是可以转移的。发现与t相邻的所有点组成了t的所有转移，必然只能够从这些点转移至t。那么这些点的dp值就可以用dp[t]转移出。一层层转移即可得到答案。
有 \(dp[x]=\dfrac{1}{in_x}\sum_{y}dp[y]+w(y,x)\)，其中 \(in_x\) 表示 x 的入度，\((y,x)\) 为一条有向边 \(y->x\)。
那么高斯消元就可以解决。

更加理性的思考这个过程。问题出在哪里？是dp的定义。
这里的顺推定义的是由s至x的距离期望。这种转移是不行的，因为没有规定究竟过程如何，这样的过程是无限多种的。同时，终止状态集合是不确定的，这是确定性计算难以接受的。
但是实际上，某些问题可以使用一些奇怪的dp状态定义达到事件互斥，进而可以计算期望。

举个例子，无向三元环，从a开始走，b结束，那么如此dp就会发现b与c的dp值相同，但这是不可能的。走到b就结束了，而走到c还可以走。

这由随机性本身决定。必须注意到期望研究的是类似于计数的却又带有无限限制的问题，而非一般的确定性问题，更不具有所谓极化问题的最优子结构之说。要跳出之前的逻辑思考。

而逆推定义的是由x到t的距离期望。考虑转移，对于x，我们研究每个多后撤一步再转移的距离期望。而这件事是可以做到的。因为不管如何，能由x到t的路径必然先由其相邻点转移到x。
这样做，起点状态是确定的，终点集合也是确定的，所以可以dp。

考虑更一般的问题。如果路径满足确定性，即类似于DAG，这种情况的确可以通过顺推进行期望计算，需要多开一个概率数组计算每一步的期望。
仅当起点、终点与转移都确定时，可以无脑正推期望。比如一些同层不转移的分层图。

将问题抽象成状态和状态之间的转移后，求解整个状态图，要从已知的状态开始计算。实际上，起点与终点都算作“已知”，但是一般终点的信息更明确，导致逆推更加容易。

dp本质上依然是对状态空间的遍历，正着/倒着，循环递推还是记忆化搜索递归，本质上都没有区别，只是在有的题目中，某一种写法更简单一些，造成了觉得“必须要正/倒推”这一错觉。