概率dp_C++详解

2023-08-11 14:38:01 来源：博客园

(相关资料图)

引入

概率 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));}

关键词：