DP xác suất

Mở đầu

DP xác suất dùng để giải quyết các bài toán về xác suất và kỳ vọng, nên xem trước Xác suất & Kỳ vọng. Thông thường, giải bài toán xác suất cần duyệt thuận, còn bài toán kỳ vọng dùng duyệt ngược. Nếu phương trình chuyển trạng thái có hậu hiệu, cần dùng Khử Gauss để tối ưu. DP xác suất cũng thường kết hợp với các kiến thức khác như trạng thái nén, DP trên cây, v.v.

DP xác suất

Dạng này dùng duyệt thuận, tức là từ trạng thái đầu đến kết quả. Tương tự DP thông thường, khó nhất vẫn là xây dựng phương trình chuyển trạng thái, chỉ là bài toán được "bọc" bởi xác suất.

Bài mẫu

Codeforces 148D Bag of mice

Có \(w\) chuột trắng và \(b\) chuột đen trong túi, công chúa và rồng lần lượt bắt chuột. Ai bắt được chuột trắng trước thì thắng, nếu hết chuột mà chưa ai bắt được chuột trắng thì rồng thắng. Công chúa bắt trước. Hỏi xác suất công chúa thắng.

Giải thích

Gọi \(f_{i,j}\) là xác suất công chúa thắng khi còn \(i\) chuột trắng, \(j\) chuột đen và đến lượt công chúa. Biên: \(f_{0,j}=0\) (hết chuột trắng, rồng thắng), \(f_{i,0}=1\) (chỉ còn chuột trắng, công chúa thắng). Xét chuyển trạng thái:

• Công chúa bắt được chuột trắng, thắng ngay, xác suất \(\dfrac{i}{i+j}\).
• Công chúa bắt chuột đen, rồng bắt chuột trắng, rồng thắng, xác suất \(\dfrac{j}{i+j}\cdot\dfrac{i}{i+j-1}\).
• Công chúa bắt chuột đen, rồng bắt chuột đen, chuột đen chạy ra, chuyển về \(f_{i,j-3}\), xác suất \(\dfrac{j}{i+j}\cdot\dfrac{j-1}{i+j-1}\cdot\dfrac{j-2}{i+j-2}\).
• Công chúa bắt chuột đen, rồng bắt chuột đen, chuột trắng chạy ra, chuyển về \(f_{i-1,j-2}\), xác suất \(\dfrac{j}{i+j}\cdot\dfrac{j-1}{i+j-1}\cdot\dfrac{i}{i+j-2}\).

Chỉ tính xác suất công chúa thắng, trường hợp 2 không cộng vào. Cần kiểm tra số lượng chuột đủ cho các trường hợp.

Mã tham khảo

#include <cstring>
#include <iomanip>
#include <iostream>
using namespace std;

using ll = long long;
int w, b;
double dp[1010][1010];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> 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];
      }
    }
  }
  cout << fixed << setprecision(9) << dp[w][b] << '\n';
  return 0;
}

Bài tập

• POJ3071 Football
• CodeForces 768D Jon and Orbs

DP kỳ vọng

Bài mẫu

POJ2096 Collecting Bugs

Một phần mềm có \(s\) module, có \(n\) loại bug. Mỗi ngày phát hiện một bug, bug này thuộc một loại và một module nào đó. Xác suất bug thuộc module \(1/s\), thuộc loại \(1/n\). Hỏi kỳ vọng số ngày để phát hiện đủ \(n\) loại bug và tất cả \(s\) module đều có bug.

Giải thích

Gọi \(f_{i,j}\) là kỳ vọng số ngày để đạt trạng thái đã có \(i\) loại bug và \(j\) module đã có bug. Trạng thái đích là \(f_{n,s}=0\). Bắt đầu truy hồi từ trạng thái đích, đáp án là \(f_{0,0}\).

Xét chuyển trạng thái:

• \(f_{i,j}\), phát hiện bug đã có, xác suất \(p_1=\dfrac{i}{n}\cdot\dfrac{j}{s}\).
• \(f_{i,j+1}\), bug loại đã có, module mới, xác suất \(p_2=\dfrac{i}{n}\cdot(1-\dfrac{j}{s})\).
• \(f_{i+1,j}\), bug loại mới, module đã có, xác suất \(p_3=(1-\dfrac{i}{n})\cdot\dfrac{j}{s}\).
• \(f_{i+1,j+1}\), bug loại mới, module mới, xác suất \(p_4=(1-\dfrac{i}{n})\cdot(1-\dfrac{j}{s})\).

Theo tính chất tuyến tính của kỳ vọng, ta có:

\[ \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\\ &= \dfrac{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} \]

Mã tham khảo

#include <iomanip>
#include <iostream>
using namespace std;
int n, s;
double dp[1010][1010];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> 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);  // 概率转移
    }
  }
  cout << fixed << setprecision(4) << dp[0][0] << '\n';
  return 0;
}

「NOIP2016」Đổi phòng học

NiuNiu học \(n\) tiết, tiết \(i\) ở phòng \(c_i\), có thể xin đổi sang \(d_i\), xác suất thành công \(p_i\), tối đa xin đổi \(m\) tiết. Sau mỗi tiết phải di chuyển sang phòng tiết tiếp theo, cho đồ thị \(v\) phòng \(e\) đường, di chuyển tốn sức. Hỏi nên xin đổi tiết nào để tổng kỳ vọng sức di chuyển là nhỏ nhất.

Giải thích

Dùng Floyd tìm đường đi ngắn nhất giữa các phòng. Định nghĩa \(f_{i,j,0/1}\) là kỳ vọng sức di chuyển nhỏ nhất khi ở tiết \(i\), đã dùng \(j\) lần đổi, trạng thái hiện tại là không đổi (0) hoặc đổi (1). Đáp án là \(\min \{f_{n,i,0},f_{n,i,1}\} ,i\in[0,m]\). Biên: \(f_{1,0,0}=f_{1,1,1}=0\).

Xét chuyển trạng thái:

• Nếu không đổi ở tiết này: \(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}))\)
• Nếu đổi ở tiết này: tương tự, xét các khả năng chuyển tiếp từ trạng thái trước.

Mã tham khảo

#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;

constexpr 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() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> v >> e;
  for (int i = 1; i <= n; i++) cin >> c[i];
  for (int i = 1; i <= n; i++) cin >> d[i];
  for (int i = 1; i <= n; i++) cin >> 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++) {
    cin >> 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));
  cout << fixed << setprecision(2) << ans;

  return 0;
}

So sánh hai bài toán trên có thể thấy, DP xác suất và DP kỳ vọng đều cần kiến thức xác suất và lập phương trình chuyển trạng thái, chỉ khác nhau ở mục tiêu tối ưu hóa hay tính giá trị.

Bài tập

• HDU3853 LOOPS
• HDU4035 Maze
• 「SCOI2008」Màn thưởng

DP có hậu hiệu

Bài mẫu

CodeForces 24D Broken robot

Cho một ma trận \(n \times m\). Robot bắt đầu ở dòng \(x\), cột \(y\), mỗi bước chọn ngẫu nhiên dừng lại, đi trái, đi phải, đi xuống. Nếu ở biên thì không ra ngoài. Hỏi kỳ vọng số bước để đến dòng cuối cùng.

Giải thích

Với \(m=1\), mỗi bước xác suất \(1/2\) không di chuyển, \(1/2\) xuống dưới, đáp án \(2\cdot (n-x)\). Gọi \(f_{i,j}\) là kỳ vọng số bước từ \((i,j)\) đến dòng \(n\). Trạng thái cuối \(f_{n,j}=0\). Xét chuyển trạng thái:

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

Chuyển đổi phương trình:

• \(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}\)

Dùng khử Gauss để giải hệ phương trình.

Mã tham khảo

#include <cstdio>
#include <cstring>
using namespace std;

constexpr int MAXN = 1e3 + 10;

double a[MAXN][MAXN], f[MAXN];
int n, m;

void solve(int x) {
  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;
}

Bài tập

• HDU 4418 Du hành thời gian
• 「HNOI2013」Dạo chơi

Tài liệu tham khảo

kuangbin Tổng kết DP xác suất

---

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:Tiphereth-A, ShaoChenHeng, Enter-tainer, ksyx, c-forrest, StudyingFather, H-J-Granger, iamtwz, imp2002, Ir1d, kenlig, LeBronGod, Marcythm, MegaOwIer, NachtgeistW, ouuan, Patchouliys, Soohti, TianKong-y, sun2snow
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply