浅谈期望 DP 的转移问题

· · 个人记录

众所周知，有别于其他 DP，在期望 DP 中我们通常采取逆推而非正推的递推形式。一般形如：

f_x = p_{x+1}\times f_{x + 1} + val_x

因为数学课最近的教学内容高度重合，以及今天下午做到了一个题，故心血来潮写下本文。。

<!--more-->

OI 中接触到的较简单的期望 DP 问题通常都属于离散型随机变量问题。相较于连续型随机变量，这类问题考察较广，对数学知识的要求较浅，如果是连续型随机变量问题，那么需要一些积分的知识。由于作者不会，本文仅讨论离散型随机变量。

我们发现，在设计转移的时候大部分都用的是逆推。此处举一个最简单的例子:机器人从第一行某个格子开始，随机往左右下三个方向走，走到最后一行的某个格子时，期望路径长度。

那么这个问题来说，我们很容易写出逆推的式子：

f_{x,y} = \frac{1}{3}(f_{x+1,y} + f_{x-1,y} + f_{x,y + 1}) + 1

我们发现，每个状态到后边的概率是相等并且好求的（即上式的 \frac{1}{3}）。但是如果倒着写，我们的式子被迫变成了如下：

f_{x,y} = p_{x - 1,y}\times f_{x -1,y}+ p_{x + 1,y}\times f_{x+1,y} + p_{x,y-1}\times f_{x,y-1} + 1

需要注意的是，p_{x,y}\neq \frac{1}{3},这个 p 实际上需要通过贝叶斯公式求出。相对来说，更加麻烦。

引用 为什么通常期望dp要倒推？ - 李煜东的回答 - 知乎 中的一段话：

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

另外，我们还可以从贝叶斯公式的角度理解一下：

设 A_i 是一组两两互斥的事件，并且有 A_{1} \cup A_{2} \cup \ldots \cup A_{2}=\Omega,P\left(A_{i}\right)>0。那么对任意事件 B \in \Omega,P(B) > 0， 有

P\left(A_{i} \mid B\right)=\dfrac{P\left(A_{i} B\right)}{P(B)}=\dfrac{P\left(A_{i}\right) P\left(B \mid A_{i}\right)}{\sum\limits_{k=1}^{n} P\left(A_{k}\right) P\left(B \mid A_{k}\right)}, i=1,2, \ldots, n

上式我们称为贝叶斯公式。

我们考虑令事件 A 为从 (1,1) 出发到达 (x,y) ，事件 B_i 就是从 (1,1) 到所有可以到 (x,y) 点（i = 0,1,2 分别对应 (x-1,y),(x+1,y),(x,y-1)），那么有

P(A) = \sum P(A|B_i)\times P(B_i)

那么我们顺推的概率 P_1 就可以表示为 P_1 = \sum P(A\mid B_i)。

接下来我们考虑逆推的概率 P_2。由贝叶斯公式得

P_2 = P\left(A \mid B_i\right)=\dfrac{P\left(A\right) P\left(B_i \mid A\right)}{\sum\limits_{k=1}^{n} P\left(A\right) P\left(B_k \mid A\right)}

那么我们考虑，当 P(A)\neq P(B) 时，P_1 \neq P_2，所以我们只能使用逆推。

（感觉后边写的有点乱，希望大佬帮忙捉虫qaq）