概率 DP
引入
概率 DP 用于解决概率问题与期望问题，建议先对 概率 & 期望 的内容有一定了解。一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环，如果定义的状态转移方程存在后效性问题，还需要用到 高斯消元 来优化。概率 DP 也会结合其他知识进行考察，例如 状态压缩，树上进行 DP 转移等。
DP 求概率
这类题目采用顺推，也就是从初始状态推向结果。同一般的 DP 类似的，难点依然是对状态转移方程的刻画，只是这类题目经过了概率论知识的包装。
题目大意：袋子里有
过程
设
- 公主抓到一只白鼠，公主赢了。概率为
- 公主抓到一只黑鼠，龙抓到一只白鼠，龙赢了。概率为
- 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，转移到
- 公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，转移到
考虑公主赢的概率，第二种情况不参与计算。并且要保证后两种情况合法，所以还要判断
实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int w, b;
double dp[1010][1010];
int main() {
scanf("%d %d", &w, &b);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= w; i++) dp[i][0] = 1; // 初始化
for (int i = 1; i <= b; i++) dp[0][i] = 0;
for (int i = 1; i <= w; i++) {
for (int j = 1; j <= b; j++) { // 以下为题面概率转移
dp[i][j] += (double)i / (i + j);
if (j >= 3) {
dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) /
(i + j - 2) * dp[i][j - 3];
}
if (i >= 1 && j >= 2) {
dp[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * i /
(i + j - 2) * dp[i - 1][j - 2];
}
}
}
printf("%.9lf\n", dp[w][b]);
return 0;
}习题
DP 求期望
例一
题目大意：一个软件有
过程
令
考虑
再根据期望的线性性质，就可以得到状态转移方程：
实现
#include <cstdio>
using namespace std;
int n, s;
double dp[1010][1010];
int main() {
scanf("%d %d", &n, &s);
dp[n][s] = 0;
for (int i = n; i >= 0; i--) {
for (int j = s; j >= 0; j--) {
if (i == n && s == j) continue;
dp[i][j] = (dp[i][j + 1] * i * (s - j) + dp[i + 1][j] * (n - i) * j +
dp[i + 1][j + 1] * (n - i) * (s - j) + n * s) /
(n * s - i * j); // 概率转移
}
}
printf("%.4lf\n", dp[0][0]);
return 0;
}例二
题目大意：牛牛要上
过程
对于这个无向连通图，先用 Floyd 求出最短路，为后续的状态转移带来便利。以移动一步为一个阶段（从第
考虑
- 如果这一阶段不换，即
- 如果这一阶段交换，即
实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int n, m, v, e;
int f[maxn][maxn], c[maxn], d[maxn];
double dp[maxn][maxn][2], p[maxn];
int main() {
scanf("%d %d %d %d", &n, &m, &v, &e);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
for (int i = 1; i <= n; i++) scanf("%lf", &p[i]);
for (int i = 1; i <= v; i++)
for (int j = 1; j < i; j++) f[i][j] = f[j][i] = 1e9;
int u, V, w;
for (int i = 1; i <= e; i++) {
scanf("%d %d %d", &u, &V, &w);
f[u][V] = f[V][u] = min(w, f[u][V]);
}
for (int k = 1; k <= v; k++)
for (int i = 1; i <= v; i++) // 前面的，按照前面的题解进行一个状态转移
for (int j = 1; j < i; j++)
if (f[i][k] + f[k][j] < f[i][j]) f[i][j] = f[j][i] = f[i][k] + f[k][j];
for (int i = 1; i <= n; i++)
for (int j = 0; j <= m; j++) dp[i][j][0] = dp[i][j][1] = 1e9;
dp[1][0][0] = dp[1][1][1] = 0;
for (int i = 2; i <= n; i++) // 有后效性方程
for (int j = 0; j <= min(i, m); j++) {
dp[i][j][0] = min(dp[i - 1][j][0] + f[c[i - 1]][c[i]],
dp[i - 1][j][1] + f[c[i - 1]][c[i]] * (1 - p[i - 1]) +
f[d[i - 1]][c[i]] * p[i - 1]);
if (j != 0) {
dp[i][j][1] = min(dp[i - 1][j - 1][0] + f[c[i - 1]][d[i]] * p[i] +
f[c[i - 1]][c[i]] * (1 - p[i]),
dp[i - 1][j - 1][1] +
f[c[i - 1]][c[i]] * (1 - p[i - 1]) * (1 - p[i]) +
f[c[i - 1]][d[i]] * (1 - p[i - 1]) * p[i] +
f[d[i - 1]][c[i]] * (1 - p[i]) * p[i - 1] +
f[d[i - 1]][d[i]] * p[i - 1] * p[i]);
}
}
double ans = 1e9;
for (int i = 0; i <= m; i++) ans = min(dp[n][i][0], min(dp[n][i][1], ans));
printf("%.2lf", ans);
return 0;
}比较这两个问题可以发现，DP 求期望题目在对具体是求一个值或是最优化问题上会对方程得到转移方式有一些影响，但无论是 DP 求概率还是 DP 求期望，总是离不开概率知识和列出、化简计算公式的步骤，在写状态转移方程时需要思考的细节也类似。
习题
有后效性 DP
题目大意：给出一个
过程
在
在行之间由于只能向下移动，是满足无后效性的。在列之间可以左右移动，在移动过程中可能产生环，不满足无后效性。 将方程变换后可以得到：
由于是逆序的递推，所以每一个
实现
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
double a[maxn][maxn], f[maxn];
int n, m;
void solve(int x) {
memset(a, 0, sizeof a);
for (int i = 1; i <= m; i++) {
if (i == 1) {
a[i][i] = 2;
a[i][i + 1] = -1;
a[i][m + 1] = 3 + f[i];
continue;
} else if (i == m) {
a[i][i] = 2;
a[i][i - 1] = -1;
a[i][m + 1] = 3 + f[i];
continue;
}
a[i][i] = 3;
a[i][i + 1] = -1;
a[i][i - 1] = -1;
a[i][m + 1] = 4 + f[i];
}
for (int i = 1; i < m; i++) {
double p = a[i + 1][i] / a[i][i];
a[i + 1][i] = 0;
a[i + 1][i + 1] -= a[i][i + 1] * p;
a[i + 1][m + 1] -= a[i][m + 1] * p;
}
f[m] = a[m][m + 1] / a[m][m];
for (int i = m - 1; i >= 1; i--)
f[i] = (a[i][m + 1] - f[i + 1] * a[i][i + 1]) / a[i][i];
}
int main() {
scanf("%d %d", &n, &m);
int st, ed;
scanf("%d %d", &st, &ed);
if (m == 1) {
printf("%.10f\n", 2.0 * (n - st));
return 0;
}
for (int i = n - 1; i >= st; i--) {
solve(i);
}
printf("%.10f\n", f[ed]);
return 0;
}习题
参考文献
贡献者：@TianKong_y@MegaOwIer@Tifa@WenzelTian@Shuhao@H-J-Granger@kenlig@imp@LeBronGod@mgt@Patchouliys@hongchenhao@邵晨恒
本页面最近更新：2/3/2023, 12:00:00 AM，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用