【资料图】
概率 DP 用于解决概率问题与期望问题，建议先对概率和期望的内容有一定了解。一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到 高斯消元 来优化。概率 DP 也会结合其他知识进行考察，例如 状态压缩，树上进行DP转移等。
求法这类题目采用顺推，也就是从初始状态推向结果。同一般的 DP 类似的，难点依然是对状态转移方程的刻画，只是这类题目经过了概率论知识的包装。
例题P4316 绿豆蛙的归宿这道题的终点很明确，那就是走到 (n) 即停止。对于期望 DP，我们一般采用逆序的方式来定义状态，即考虑从当前状态到达终点的期望代价。因为在大多数情况下，终点不唯一，而起点是唯一的。我们定义 (dp(i))为从 (i) 出发走到终点 (n) 的路径期望总长度，根据全期望公式，得到（设 (G_i)为从 (i) 的边的集合）：\(dp(i) = \sum\limits_{e\in G_i}\frac{dp(e_{to}) + e_{const}}{|G_i|}\)因为这是一个有向无环图，每个点需要其能到达的点的状态，故我们采用拓扑序的逆序进行计算即可。
#include using namespace std;const int N = 100000, M = 2 * N;int n, m;struct node { int v, w;};vector e[N];int d[N]; double f[N]; double dfs(int u) { if (f[u] >= 0) return f[u]; f[u] = 0; for (auto [v, w] : e[u]) { f[u] += (w + dfs(v)) / d[u]; } return f[u];}int main() { memset(f, -1, sizeof(f)); cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; e[u].push_back(node{v, w}); d[u]++; } printf("%.2f\n", dfs(1));} 
