DP xác suất & kỳ vọng

Wiki › Thuật toán › Quy hoạch động (DP)

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

DP xác suất (Probability DP) tính xác suất hoặc kỳ vọng (expected value) của các sự kiện ngẫu nhiên thông qua quy hoạch động. Trạng thái DP lưu xác suất hoặc kỳ vọng thay vì giá trị tối ưu.

Ôn lại kiến thức xác suất cần thiết

Khái niệm	Công thức
Xác suất tổng	$P (A \cup B) = P (A) + P (B) - P (A \cap B)$
Xác suất có điều kiện	$P (A ∣ B) = P (A \cap B) / P (B)$
Kỳ vọng tuyến tính	$E [X + Y] = E [X] + E [Y]$ (luôn đúng)
Kỳ vọng toàn phần	$E [X] = \sum_{i} P (S = s_{i}) \cdot E [X ∣ S = s_{i}]$

Dạng 1: DP xác suất tiến (Forward)

Tư duy: Bắt đầu từ trạng thái đã biết, lan truyền xác suất về phía trước.

prob[state] = xác suất đạt được state đó

Ví dụ: Đồng xu

Tung $n$ đồng xu, mỗi đồng có xác suất $p$ ra mặt ngửa. Tính xác suất có đúng $k$ mặt ngửa.

// dp[i][j] = xác suất sau i lần tung, có j mặt ngửa
vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
dp[0][0] = 1.0;

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        if (dp[i][j] == 0) continue;
        dp[i+1][j+1] += dp[i][j] * p;      // ngửa
        dp[i+1][j]   += dp[i][j] * (1 - p); // sấp
    }
}
cout << dp[n][k] << "\n";
// Hoặc dùng công thức C(n,k) * p^k * (1-p)^(n-k)

Dạng 2: DP kỳ vọng ngược (Backward / Reverse)

Tư duy: Bắt đầu từ trạng thái đích (kỳ vọng = 0), tính ngược về trạng thái ban đầu.

E[state] = kỳ vọng số bước/chi phí để đến đích từ state

Ví dụ: Bài toán con súc sắc

Tung xúc xắc 6 mặt. Mỗi lần tung được điểm bằng số mặt. Dừng lại bất cứ lúc nào hoặc tung tiếp. Chiến lược tối ưu để tối đa hóa điểm kỳ vọng?

// E = kỳ vọng điểm với chiến lược tối ưu
// Nếu điểm hiện tại x > E: dừng (giữ x)
// Nếu x <= E: tung tiếp

// E = (1/6) * sum(max(i, E)) với i từ 1 đến 6
// Giải: E = (1/6) * (sum_{i>E} i + count_{i<=E} * E)
// Bằng toán học: E = 14/3 ≈ 4.67 (dừng nếu >= 4)
double E = 0;
for (int iter = 0; iter < 1000; iter++) {
    double newE = 0;
    for (int i = 1; i <= 6; i++)
        newE += max((double)i, E);
    newE /= 6.0;
    E = newE;
}
cout << fixed << setprecision(6) << E << "\n";

Dạng 3: DP kỳ vọng với phương trình tuyến tính

Một số bài có trạng thái phụ thuộc lẫn nhau (circular dependency), cần giải hệ phương trình.

Ví dụ: Gambler's Ruin

Có $n$ đồng. Mỗi bước: xác suất $p$ được thêm 1 đồng, xác suất $1 - p$ mất 1 đồng. Dừng khi có $0$ hoặc $N$ đồng. Tính xác suất thắng (đạt $N$ đồng) khi bắt đầu với $k$ đồng.

P[k] = p * P[k+1] + (1-p) * P[k-1]
P[0] = 0, P[N] = 1

// Giải hệ phương trình tuyến tính
// Với p != 0.5: P[k] = (1 - (q/p)^k) / (1 - (q/p)^N)
// Với p = 0.5: P[k] = k / N
double p = 0.6, q = 1 - p;
int k = 5, N = 10;
double ratio = q / p;
double prob;
if (abs(p - 0.5) < 1e-9)
    prob = (double)k / N;
else
    prob = (1 - pow(ratio, k)) / (1 - pow(ratio, N));
cout << prob << "\n";

Kỹ thuật giải hệ dùng Gaussian Elimination khi không có công thức đóng:

// Xây ma trận [A|b] và giải Ax = b
// Mỗi phương trình: E[i] = sum_j (p_ij * E[j]) + c_i
// Biến đổi: E[i] - sum_j (p_ij * E[j]) = c_i

Dạng 4: Kỳ vọng bước trên chuỗi Markov

Bài toán: Cho đồ thị có hướng với xác suất chuyển. Tính kỳ vọng số bước từ nút $s$ đến nút $t$ .

Trạng thái: E[u] = kỳ vọng số bước từ $u$ đến $t$ .

E[t] = 0
E[u] = 1 + sum_{v: có cạnh u->v} p(u,v) * E[v]

Nếu đồ thị là DAG, có thể tính theo thứ tự topo ngược:

// Topo sort ngược, tính E[u] từ E[v]
vector<double> E(n, 0);
// Duyệt theo thứ tự topo ngược
for (int u : reverse_topo) {
    if (u == t) { E[u] = 0; continue; }
    E[u] = 1;
    for (auto [v, prob] : adj[u])
        E[u] += prob * E[v];
}

Nếu có chu trình: cần Gaussian Elimination.

Ví dụ đầy đủ: Xúc xắc và tổng mục tiêu

Bài toán: Tung xúc xắc $k$ mặt lặp đi lặp lại. Tính xác suất tổng đúng bằng $n$ tại một thời điểm nào đó.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;  // mục tiêu n, xúc xắc k mặt

    vector<double> dp(n + 1, 0);
    dp[0] = 1.0;  // bắt đầu tại 0

    for (int i = 1; i <= n; i++) {
        for (int face = 1; face <= k && face <= i; face++) {
            dp[i] += dp[i - face] / k;
        }
    }
    cout << fixed << setprecision(9) << dp[n] << "\n";
}

Ví dụ: Kỳ vọng số lần thử đến khi thu thập đủ bộ (Coupon Collector)

Bài toán: Mỗi lần lấy ngẫu nhiên 1 trong $n$ phần tử (đều nhau). Kỳ vọng số lần lấy để có đủ $n$ phần tử khác nhau?

Trạng thái: E[i] = kỳ vọng số lần lấy thêm khi đã có $i$ phần tử khác nhau.

E[n] = 0
E[i] = 1 + (i/n) * E[i] + ((n-i)/n) * E[i+1]
     = n/(n-i) + E[i+1]

double expected = 0;
for (int i = 0; i < n; i++)
    expected += (double)n / (n - i);
// expected = n * H_n (n nhân harmonic number thứ n)
cout << fixed << setprecision(6) << expected << "\n";

Kết quả: $E = n \cdot H_{n} = n \cdot (1 + 1 / 2 + 1 / 3 + \dots + 1 / n)$ .

Làm việc với modulo

Nhiều bài yêu cầu kết quả modulo $10^{9} + 7$ (dưới dạng phân số $p / q$ ). Dùng nghịch đảo modular:

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long inv(long long a) { return power(a, MOD - 2, MOD); }

// Thay a/b bằng a * inv(b) % MOD
long long prob = numerator * inv(denominator) % MOD;

Tổng kết

Dạng bài	Kỹ thuật
Xác suất đạt trạng thái	DP tiến, lan truyền xác suất
Kỳ vọng số bước đến đích	DP ngược từ đích
Hệ có chu trình	Gaussian Elimination
Coupon collector	Công thức tổng điều hòa
Kết quả dưới dạng modulo	Nghịch đảo modular

Lưu ý quan trọng:

Luôn kiểm tra tổng xác suất từ một trạng thái = 1.
Kỳ vọng tuyến tính ( $E [X + Y] = E [X] + E [Y]$ ) thường giúp đơn giản hóa bài toán đáng kể.
Với bài yêu cầu modulo, không dùng double — dùng nghịch đảo modular.

Bình luận

Không có bình luận tại thời điểm này.