概率与期望DP

概率期望DP

1、概率DP

由于概率的计算具有线性性质，因此建立递推关系，利用动态规划的方法进行快速计算，这就是概率DP。

动态规划问题中状态设计和状态转移方程是关键。常见的状态会与当前位置、剩余步数、累积结果等相关，一般我们将问题作为状态，认为 $dp[i]=$ 到达状态 $i$ 的概率，即可通过递推得到转移方程。

概率DP相对简单，通常会从已知的初始状态出发, 最初的起点概率设定为 $1$，求目标状态的概率，因此状态转移方程通常是如下形式。

当前存在一个从 $x$ 点到 $y$ 点的转移，则 $f[y] += f[x] * P(x \to y)$。

2、期望DP

大部分的情况下，我们在做求期望的DP时候会采取一个截然相反的状态转移过程，采用倒推的思路来求解问题。

期望 DP 要倒推的原因通常是：初态（起点）唯一，目标状态（终点）不唯一。

期望的定义是所有可能的结果的加权求和，因此如果正向进行期望的转移，结果的计算较为复杂，而由于起点是唯一的



大部分的情况下，我们在做求期望的DP时候会采取一个截然相反的状态转移过程，采用倒推的思路来求解问题。

期望 DP 要倒推的原因通常是：初态（起点）唯一，目标状态（终点）不唯一。

期望的定义是所有可能的结果的加权求和，因此如果正向进行期望的转移，结果的计算较为复杂，而由于起点是唯一的，概率必定为 $1$,一定可以得到答案。

期望 DP 在转移的实现方式上和普通的 DP 无异，但是状态转移方程需要结合概率期望的数学公式来完成。

期望DP常见的有两种承载形式：

线性期望DP

此情况下，状态 $1$ 到状态 $n$ 线性排布，直接从后往前倒推进行转移即可。



$DAG$ 上期望DP

有向无环图的结构存在拓扑序，可以在有向无环图上通过倒退进行期望DP的求解。由于是一个非线性结构，我们倒退时候需要保证遵循图形的拓扑序。 因此可以对图形先进行拓扑排序，而后逆序遍历拓扑序的结果从而实现 $DAG$ 上的倒推。



如果题目中的有向无环图是一颗树的话，那么直接对树进行递归遍历实现期望的倒推求解即可。

3、循环依赖期望DP

以上两种DP的前提都是概率和期望的计算不存在循环依赖，也就是说概率和期望的状态转移方程是单向的，但是期望DP中存在这样一个特殊的类别，期望的传导计算形成了一个环，此时期望DP存在有循环依赖，需要特殊的方式来处理：



例如一个机器人从 $1$ 号点出发，既可以向左移动，又可以向右移动，那么存在 $f[i] \to f[i + 1]$的转移，也存在 $f[i + 1] \to f[i]$ 的转移，机器人可能会在两个点之间进行反复的移动，此时期望的计算因为后效性受到阻碍。



对于有循环依赖的DP，通常有以下 $3$ 种解决途径：



模拟仿真(求近似解）

对于数据范围相对小的习题，或者目标是其中部分的测试点，可以考虑通过进行多轮 DP 转移，令答案不断地逼近正确答案，每一个点的期望会在不断的 DP 转移中不断地向正解收敛，此法可以用于获取暴力分。



数学公式化简

结合题目给出的限制，将原有的转移方程化简成一个不存在循环依赖的式子，而后进行期望DP的转移完成题目的求解



例题：Alice's Adventures in the Rabbit Hol

通过公式化简之后可以通过朴素的树形dp来完成期望的求解



解方程组求解

对于每一个点的期望，我们可以将其看作是未知数，将其带入推导出的状态转移方程。对于循环依赖的传导环的每一点都能得到一个方程，联立之后得到一个方程组，解方程组之后可以得到每一个期望的值。

解方程组的常用解法为高斯消元，当题目未知数数量较小的情况下也可以手动消元求解。



例题：Broken robot

对于同一行之间的不同位置，由于机器人可以左右移动产生了循环依赖，因此可以将同一行每个位置的期望设为未知数建立方程组，使用高斯消元求解。

【前置知识点】
1、概率期望

【思维导图】







【题目知识点分类】