核心逻辑与数学原理
期望动态规划（Expectation DP）是处理带有“决策路径随机性”或“后继状态不确定”问题的核心算法工具。它与常规动态规划的最大区别在于，状态转移不是确定性的选择（Max/Min），而是对所有可能后继状态代价的加权平均（求和归结）。
1. 期望 DP 的转移机理
设当前处于状态 $u$，它有若干条分立的随机转移路径通往后继状态集合 $to(u)$。对于每一个后继状态 $v \in to(u)$，转移发生的概率为 $p(u \to v)$，转移本身付出的代价（如步数、花费、权值）为 $w(u \to v)$。
根据数学期望的定义以及全期望公式，从状态 $u$ 出发直到终点的期望总代价 $f[u]$ 满足以下代数方程：
$$f[u] = \sum_{v \in to(u)} p(u \to v) \cdot \Big( f[v] + w(u \to v) \Big)$$
利用概率归一化性质 $\sum p(u \to v) = 1$，该公式常被进一步化简为便于代码实现的经典形式：
$$f[u] = \left( \sum_{v \in to(u)} p(u \to v) \cdot f[v] \right) + \sum_{v \in to(u)} p(u \to v) \cdot w(u \to v)$$
2. 为什么期望 DP 大多采用“倒推（逆向移项）”？
在常规 DP 中，我们习惯于“正推”（从起点推向终点）。但在期望 DP 中，正推往往会导致逻辑崩溃。
- 正推的困境：如果我们定义 $f[u]$ 为从起点走到状态 $u$ 的期望代价。那么在计算 $f[u]$ 时，我们不仅需要知道前驱状态的期望，还需要知道走到当前状态 $u$ 的绝对概率。这就必须同时维护一个概率 DP，极易导致状态高度耦合。
- 倒推的破局：如果我们定义 $f[u]$ 为从状态 $u$ 出发走到终点的期望总代价。
- 终点状态极其明确：终点 $T$ 本身到终点的代价显然为 $0$，即边界条件 $f[T] = 0$ 恒成立。
- 彻底脱离概率耦合：由于 $f[u]$ 描述的是“未来的期望”，它与“过去是以多大概率走到状态 $u$ 的”完全无关。这就成功实现了状态解耦。
状态设计与算法推导
1. DAG 上的无环倒推
如果状态转移依赖关系构成一个有向无环图（DAG），我们可以直接利用逆向拓扑排序（或记忆化搜索），从终点 $T$ 开始倒推填表。
- 状态方程：
$$f[u] = \sum_{(u, v) \in E} p(u \to v) \cdot (f[v] + w(u \to v))$$
2. 包含“自环/环路”的期望 DP 与高斯消元
许多期望问题中存在“原地踏步”或“状态循环”的特征（例如：投掷骰子点数不对则原地不动，或者在图上随机游走）。此时状态转移方程会出现循环依赖，即 $f[u]$ 的代数式中包含 $f[u]$ 本身或其他互相包含的未知数。这导致无法直接顺序填表。
破局策略：
- 单点自环化简：若仅存在当前状态向自身的转移（概率为 $p_{\text{self}}$），直接进行代数移项。
$$f[u] = p_{\text{self}} \cdot (f[u] + w_{\text{self}}) + \sum_{v \neq u} p(u \to v) \cdot (f[v] + w(u \to v))$$
把所有含 $f[u]$ 的项移到等左侧并提取系数 $(1 - p_{\text{self}})$，做除法即可消除自环阻碍。 2. 强连通块环路（全图游走）：若状态间形成了复杂的网状环路，则放弃递推，直接将每个状态 $f[u]$ 视作一个未知数 $x_u$，根据转移拓扑关系列出 $N$ 个一元一次方程，组建出矩阵，直接使用高斯消元（Gaussian Elimination）在 $O(N^3)$ 复杂度内暴力求解。
C++ 标准源码
核心实现：记忆化搜索倒推期望 DP
针对典型具有分治结构的期望状态，使用记忆化搜索能够自动完成逆向拓扑序流转。
#include <iostream>
#include <vector>
#include <iomanip>
struct Edge {
int to;
double prob; // 转移概率
double weight; // 转移代价
};
const int MAXN = 100000;
std::vector<Edge> graph[MAXN + 5];
double f[MAXN + 5];
bool visited[MAXN + 5];
int target_node;
// 记忆化搜索：求从 u 出发走到 target_node 的期望总代价
double get_expectation(int u) {
if (u == target_node) return 0.0; // 终点边界：到自身的期望代价为 0
if (visited[u]) return f[u]; // 拦截已计算状态
visited[u] = true;
double total_exp = 0.0;
for (const auto &edge : graph[u]) {
int v = edge.to;
// 核心倒推公式：p * (f[v] + weight)
total_exp += edge.prob * (get_expectation(v) + edge.weight);
}
f[u] = total_exp;
return f[u];
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m, start_node;
if (std::cin >> n >> m >> start_node >> target_node) {
for (int i = 0; i < m; ++i) {
int u, v;
double p, w;
std::cin >> u >> v >> p >> w;
graph[u].push_back({v, p, w});
}
double ans = get_expectation(start_node);
std::cout << std::fixed << std::setprecision(6) << ans << "\n";
}
return 0;
}NOIP 实战避坑指南
- 错将终点状态初始化为非零值或正向赋初值
部分选手习惯了正向思维，在初始化时将起点
f[S] = 0，然后试图向后更新。这样写会导致在计算分支时，由于无法预知后继节点的全局收敛值，算出来的数字完全背离期望的定义。请务必牢记：期望 DP 的天然确定性边界在终点，f[T] = 0是递推的始发引擎。 - 高斯消元时未处理不可达状态导致的自由元崩溃 在面对需要高斯消元的图论随机游走题目时，图里可能存在一些由于单向联通导致永远不可能到达终点的死结节点，或者从起点根本走不到的孤立节点。这些节点对应的未知数方程可能会引发矩阵行列式为 $0$（出现多解或无解）。在送入高斯消元前，必须先用 BFS/DFS 跑一遍正反向连通性判定，将无效状态剔除出方程组。
经典 NOIP/洛谷 真题
1. 洛谷 P4550 收集邮票
- 题意描述：有 $n$ 种不同的邮票，每次购买其中一种。已知每种邮票被买到的概率均为 $\frac{1}{n}$。第 $r$ 次购买需要支付 $r$ 元。求收集齐所有 $n$ 种邮票所需花费的数学期望。
- 问题本质：双状态耦合倒推期望 DP。
- 核心解题思路：由于购买代价与购买次数强绑定，我们不能只维护花费期望。利用分治，定义 $f[i]$ 表示已经收集了 $i$ 种邮票，要凑齐剩下所有邮票所需的期望购买次数；定义 $g[i]$ 表示已经收集了 $i$ 种邮票，凑齐剩下邮票所需的期望花费。通过考虑下一次购买是买到重复的（概率 $\frac{i}{n}$）还是买到全新的（概率 $\frac{n-i}{n}$），可以列出倒推方程：
$$f[i] = \frac{i}{n} f[i] + \frac{n-i}{n} f[i+1] + 1 \implies f[i] = f[i+1] + \frac{n}{n-i}$$
利用 $f[i]$ 作为代数系数再去驱动 $g[i]$ 的状态转移，从 $n$ 倒推到 $0$，$g[0]$ 即为最终解。
2. 洛谷 P1850 [NOIP2016 提高组] 换教室
- 题意描述：有 $n$ 节课，每节课初始在教室 $c_i$，可申请更换到 $d_i$，更换成功的概率为 $k_i$。最多只能提出 $m$ 次申请。求在最优申请策略下，跑完这 $n$ 节课所经过的总距离的最小期望值。
- 问题本质：多维状态决策期望 DP。
- 核心解题思路：本题将控制流决策（最优选择申请哪些课）与期望有机融合。定义状态 $f[i][j][0/1]$ 表示当前正在安排第 $i$ 节课，已经用掉了 $j$ 次申请机会，且对第 $i$ 节课 0 (没申请) / 1 (申请了) 时，完成后续所有课程的最小期望总距离。转移时，由于第 $i$ 节课和第 $i+1$ 节课的实际教室去向分别有 $2 \times 2 = 4$ 种概率组合情况，我们需要用时空两点的最短路距离（通过 Floyd 预处理）与概率 $k_i, k_{i+1}$ 进行全期望排列组合累加，并对“申请”或“不申请”取
std::min。这不仅是期望倒推的经典，也是 NOIP 历史上最硬核的期望 DP 真题之一。