跳转至

概率 DP

引入

概率 DP 用於解決概率問題與期望問題，建議先對 概率 & 期望 的內容有一定了解。一般情況下，解決概率問題需要順序循環，而解決期望問題使用逆序循環，如果定義的狀態轉移方程存在後效性問題，還需要用到 高斯消元 來優化。概率 DP 也會結合其他知識進行考察，例如 狀態壓縮，樹上進行 DP 轉移等。

DP 求概率

這類題目採用順推，也就是從初始狀態推向結果。同一般的 DP 類似的，難點依然是對狀態轉移方程的刻畫，只是這類題目經過了概率論知識的包裝。

例題 Codeforces 148 D Bag of mice

題目大意：袋子裏有 \(w\) 只白鼠和 \(b\) 只黑鼠，公主和龍輪流從袋子裏抓老鼠。誰先抓到白色老鼠誰就贏，如果袋子裏沒有老鼠了並且沒有誰抓到白色老鼠，那麼算龍贏。公主每次抓一隻老鼠，龍每次抓完一隻老鼠之後會有一隻老鼠跑出來。每次抓的老鼠和跑出來的老鼠都是隨機的。公主先抓。問公主贏的概率。

過程

設 \(f_{i,j}\) 為輪到公主時袋子裏有 \(i\) 只白鼠，\(j\) 只黑鼠，公主贏的概率。初始化邊界，\(f_{0,j}=0\) 因為沒有白鼠了算龍贏，\(f_{i,0}=1\) 因為抓一隻就是白鼠，公主贏。 考慮 \(f_{i,j}\) 的轉移：

  • 公主抓到一隻白鼠，公主贏了。概率為 \(\frac{i}{i+j}\)；
  • 公主抓到一隻黑鼠，龍抓到一隻白鼠，龍贏了。概率為 \(\frac{j}{i+j}\cdot \frac{i}{i+j-1}\)；
  • 公主抓到一隻黑鼠，龍抓到一隻黑鼠，跑出來一隻黑鼠，轉移到 \(f_{i,j-3}\)。概率為 \(\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{j-2}{i+j-2}\)；
  • 公主抓到一隻黑鼠，龍抓到一隻黑鼠，跑出來一隻白鼠，轉移到 \(f_{i-1,j-2}\)。概率為 \(\frac{j}{i+j}\cdot\frac{j-1}{i+j-1}\cdot\frac{i}{i+j-2}\)；

考慮公主贏的概率，第二種情況不參與計算。並且要保證後兩種情況合法，所以還要判斷 \(i,j\) 的大小，滿足第三種情況至少要有 3 只黑鼠，滿足第四種情況要有 1 只白鼠和 2 只黑鼠。

實現

參考實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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 求期望

例一

例題 POJ2096 Collecting Bugs

題目大意：一個軟件有 \(s\) 個子系統，會產生 \(n\) 種 bug。某人一天發現一個 bug，這個 bug 屬於某種 bug 分類，也屬於某個子系統。每個 bug 屬於某個子系統的概率是 \(\frac{1}{s}\)，屬於某種 bug 分類的概率是 \(\frac{1}{n}\)。求發現 \(n\) 種 bug，且 \(s\) 個子系統都找到 bug 的期望天數。

過程

令 \(f_{i,j}\) 為已經找到 \(i\) 種 bug 分類，\(j\) 個子系統的 bug，達到目標狀態的期望天數。這裏的目標狀態是找到 \(n\) 種 bug 分類，\(s\) 個子系統的 bug。那麼就有 \(f_{n,s}=0\)，因為已經達到了目標狀態，不需要用更多的天數去發現 bug 了，於是就以目標狀態為起點開始遞推，答案是 \(f_{0,0}\)。

考慮 \(f_{i,j}\) 的狀態轉移：

  • \(f_{i,j}\)，發現一個 bug 屬於已經發現的 \(i\) 種 bug 分類，\(j\) 個子系統，概率為 \(p_1=\frac{i}{n}\cdot\frac{j}{s}\)
  • \(f_{i,j+1}\)，發現一個 bug 屬於已經發現的 \(i\) 種 bug 分類，不屬於已經發現的子系統，概率為 \(p_2=\frac{i}{n}\cdot(1-\frac{j}{s})\)
  • \(f_{i+1,j}\)，發現一個 bug 不屬於已經發現 bug 分類，屬於 \(j\) 個子系統，概率為 \(p_3=(1-\frac{i}{n})\cdot\frac{j}{s}\)
  • \(f_{i+1,j+1}\)，發現一個 bug 不屬於已經發現 bug 分類，不屬於已經發現的子系統，概率為 \(p_4=(1-\frac{i}{n})\cdot(1-\frac{j}{s})\)

再根據期望的線性性質，就可以得到狀態轉移方程：

\[ \begin{aligned} f_{i,j} &= p_1\cdot f_{i,j}+p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1} + 1\\ &= \frac{p_2\cdot f_{i,j+1}+p_3\cdot f_{i+1,j}+p_4\cdot f_{i+1,j+1}+1}{1-p_1} \end{aligned} \]

實現

參考實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#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;
}

例二

例題 「NOIP2016」換教室

題目大意：牛牛要上 \(n\) 個時間段的課，第 \(i\) 個時間段在 \(c_i\) 號教室，可以申請換到 \(d_i\) 號教室，申請成功的概率為 \(p_i\)，至多可以申請 \(m\) 節課進行交換。第 \(i\) 個時間段的課上完後要走到第 \(i+1\) 個時間段的教室，給出一張圖 \(v\) 個教室 \(e\) 條路，移動會消耗體力，申請哪幾門課程可以使他因在教室間移動耗費的體力值的總和的期望值最小，也就是求出最小的期望路程和。

過程

對於這個無向連通圖，先用 Floyd 求出最短路，為後續的狀態轉移帶來便利。以移動一步為一個階段（從第 \(i\) 個時間段到達第 \(i+1\) 個時間段就是移動了一步），那麼每一步就有 \(p_i\) 的概率到 \(d_i\)，不過在所有的 \(d_i\) 中只能選 \(m\) 個，有 \(1-p_i\) 的概率到 \(c_i\)，求出在 \(n\) 個階段走完後的最小期望路程和。 定義 \(f_{i,j,0/1}\) 為在第 \(i\) 個時間段，連同這一個時間段已經用了 \(j\) 次換教室的機會，在這個時間段換（1）或者不換（0）教室的最小期望路程和，那麼答案就是 \(\min \{f_{n,i,0},f_{n,i,1}\} ,i\in[0,m]\)。注意邊界 \(f_{1,0,0}=f_{1,1,1}=0\)。

考慮 \(f_{i,j,0/1}\) 的狀態轉移：

  • 如果這一階段不換，即 \(f_{i,j,0}\)。可能是由上一次不換的狀態轉移來的，那麼就是 \(f_{i-1,j,0}+w_{c_{i-1},c_{i}}\), 也有可能是由上一次交換的狀態轉移來的，這裏結合條件概率和全概率的知識分析可以得到 \(f_{i-1,j,1}+w_{d_{i-1},c_{i}}\cdot p_{i-1}+w_{c_{i-1},c_{i}}\cdot (1-p_{i-1})\)，狀態轉移方程就有
\[ \begin{aligned} f_{i,j,0}=min(f_{i-1,j,0}+w_{c_{i-1},c_{i}},f_{i-1,j,1}+w_{d_{i-1},c_{i}}\cdot p_{i-1}+w_{c_{i-1},c_{i}}\cdot (1-p_{i-1})) \end{aligned} \]
  • 如果這一階段交換，即 \(f_{i,j,1}\)。類似地，可能由上一次不換的狀態轉移來，也可能由上一次交換的狀態轉移來。那麼遇到不換的就乘上 \((1-p_i)\)，遇到交換的就乘上 \(p_i\)，將所有會出現的情況都枚舉一遍出進行計算就好了。這裏不再贅述各種轉移情況，相信通過上一種階段例子，這裏的狀態轉移應該能夠很容易寫出來。

實現

參考實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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

CodeForces 24 D Broken robot

題目大意：給出一個 \(n \times m\) 的矩陣區域，一個機器人初始在第 \(x\) 行第 \(y\) 列，每一步機器人會等概率地選擇停在原地，左移一步，右移一步，下移一步，如果機器人在邊界則不會往區域外移動，問機器人到達最後一行的期望步數。

過程

在 \(m=1\) 時每次有 \(\frac{1}{2}\) 的概率不動，有 \(\frac{1}{2}\) 的概率向下移動一格，答案為 \(2\cdot (n-x)\)。 設 \(f_{i,j}\) 為機器人機器人從第 i 行第 j 列出發到達第 \(n\) 行的期望步數，最終狀態為 \(f_{n,j}=0\)。 由於機器人會等概率地選擇停在原地，左移一步，右移一步，下移一步，考慮 \(f_{i,j}\) 的狀態轉移：

  • \(f_{i,1}=\frac{1}{3}\cdot(f_{i+1,1}+f_{i,2}+f_{i,1})+1\)
  • \(f_{i,j}=\frac{1}{4}\cdot(f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j})+1\)
  • \(f_{i,m}=\frac{1}{3}\cdot(f_{i,m}+f_{i,m-1}+f_{i+1,m})+1\)

在行之間由於只能向下移動，是滿足無後效性的。在列之間可以左右移動，在移動過程中可能產生環，不滿足無後效性。 將方程變換後可以得到：

  • \(2f_{i,1}-f_{i,2}=3+f_{i+1,1}\)
  • \(3f_{i,j}-f_{i,j-1}-f_{i,j+1}=4+f_{i+1,j}\)
  • \(2f_{i,m}-f_{i,m-1}=3+f_{i+1,m}\)

由於是逆序的遞推，所以每一個 \(f_{i+1,j}\) 是已知的。 由於有 \(m\) 列，所以右邊相當於是一個 \(m\) 行的列向量，那麼左邊就是 \(m\) 行 \(m\) 列的矩陣。使用增廣矩陣，就變成了 m 行 m+1 列的矩陣，然後進行 高斯消元 即可解出答案。

實現

參考實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}

習題

參考文獻

kuangbin 概率 DP 總結

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用