Wiki › Thuật toán › Quy hoạch động (DP) › DP xác suất & kỳ vọng

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

huunguyen Updated Tháng sáu 1, 2026

DP xác suất & kỳ vọng (Probability / Expected-value DP) dùng quy hoạch động để tính xác suất một sự kiện xảy ra hoặc kỳ vọng (giá trị trung bình) của một đại lượng ngẫu nhiên. Khác với DP tối ưu (lưu min/max), ở đây trạng thái DP lưu một số thực trong $[0, 1]$ (xác suất) hoặc kỳ vọng. Nhờ chia bài toán thành các trạng thái con và tận dụng tính chất tuyến tính của kỳ vọng, ta tránh được việc liệt kê toàn bộ không gian mẫu có kích thước hàm mũ — ví dụ tính phân bố tổng của $n$ xúc xắc trong $O (n \cdot S)$ thay vì $O (6^{n})$ .

Ý tưởng / Trực giác

Mọi bài DP xác suất/kỳ vọng đều dựa trên hai công cụ nền tảng của lý thuyết xác suất, và chính chúng giải thích vì sao việc cộng dồn theo trạng thái lại đúng.

1. Luật xác suất toàn phần. Nếu từ trạng thái hiện tại ta đi tới các trạng thái rời nhau $s_{1}, s_{2}, \dots$ với xác suất $p_{1}, p_{2}, \dots$ (tổng bằng 1), thì xác suất đạt một sự kiện $A$ là

$P (A) = \sum_{i} p_{i} \cdot P (A ∣ đã sang s_{i}) .$

Đây chính là lý do công thức DP có dạng "cộng các nhánh con nhân với xác suất nhánh". Vì các nhánh rời nhau và phủ kín, không có sự kiện nào bị đếm trùng hay bỏ sót — đó là điều kiện để DP cộng dồn cho kết quả đúng.

2. Tính tuyến tính của kỳ vọng. $E [X + Y] = E [X] + E [Y]$ luôn đúng, kể cả khi $X, Y$ phụ thuộc nhau. Suy rộng cho kỳ vọng có điều kiện:

$E [X] = \sum_{i} P (sang s_{i}) \cdot (chi phí bước này + E [X ∣ s_{i}]) .$

Với bài "kỳ vọng số bước đến đích", ta đặt $E [u]$ = kỳ vọng số bước từ $u$ tới đích. Mỗi bước tốn 1 và đi sang $v$ với xác suất $p (u, v)$ , nên

$E [u] = 1 + \sum_{v} p (u, v) E [v], E [đích] = 0 .$

Chiều tính toán quyết định kỹ thuật:

Trạng thái chỉ phụ thuộc trạng thái "trước" (DAG, thứ tự thời gian) → DP một chiều thẳng, gọi là forward (lan truyền xác suất từ đầu) hoặc backward (tính ngược từ đích).
Trạng thái phụ thuộc lẫn nhau thành chu trình (ví dụ "thử lại" làm $E [i]$ xuất hiện ở cả hai vế) → phải giải hệ phương trình tuyến tính (Gauss) hoặc biến đổi đại số để cô lập biến.

Nắm được "bài này có chu trình hay không" là chìa khoá chọn đúng cách cài.

Ví dụ chạy tay

Xét bài quen thuộc: xác suất tổng của $n$ xúc xắc 6 mặt rơi vào từng giá trị. Đặt dp[i][s] = xác suất sau khi tung $i$ con, tổng bằng $s$ . Công thức (luật toàn phần, mỗi mặt có xác suất $\frac{1}{6}$ ):

$d p [i] [s] = \sum_{f = 1}^{6} \frac{1}{6} d p [i - 1] [s - f] .$

Chạy tay với $n = 2$ . Khởi tạo dp[0][0] = 1 (chưa tung, tổng 0 chắc chắn). Sau 1 con, mỗi tổng $1 . .6$ có xác suất $\frac{1}{6} \approx 0.167$ :

        s: 0     1     2     3     4     5     6
dp[0]:   1.00    .     .     .     .     .     .
dp[1]:    .    .167  .167  .167  .167  .167  .167

Sau 2 con, ta điền dp[2][s]. Lấy ô đang xét $s = 4$ (đánh dấu [*]): các cách ra tổng 4 là $(1, 3), (2, 2), (3, 1)$ — tức cộng dp[1][3] + dp[1][2] + dp[1][1], mỗi cái nhân $\frac{1}{6}$ :

$d p [2] [4] = \frac{1}{6} (0.167 + 0.167 + 0.167) = \frac{3}{36} \approx 0.083 .$

        s:  2     3     4      5     6     7     8 ...
dp[2]:    .028  .056 [.083] .111  .139  .167  .139 ...
                       ^^^
            tổng 4 = (1,3)+(2,2)+(3,1) = 3/36

Đỉnh phân bố tại $s = 7$ với $6 / 36 \approx 0.167$ , đối xứng hai bên — đúng trực giác "tổng 2 xúc xắc hay ra 7 nhất". Cộng dp[2][9] + dp[2][10] = 4/36 + 3/36 = 7/36 ≈ 0.194, khớp ví dụ của bài diceprob.

Cài đặt

Mẫu 1 — DP xác suất tiến (phân bố tổng xúc xắc, dùng cho diceprob):

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

int main() {
    int n, a, b;
    cin >> n >> a >> b;            // n xúc xắc, hỏi P(tổng thuộc [a,b])

    // dp[s] = xác suất tổng hiện tại bằng s (cuộn 1 chiều theo số con đã tung)
    vector<double> dp(6 * n + 1, 0.0);
    dp[0] = 1.0;                   // chưa tung: tổng 0 với xác suất 1

    for (int i = 1; i <= n; i++) {
        vector<double> nxt(6 * n + 1, 0.0);
        for (int s = i - 1; s <= 6 * (i - 1); s++) {
            if (dp[s] == 0) continue;
            for (int f = 1; f <= 6; f++)   // gieo con thứ i ra mặt f
                nxt[s + f] += dp[s] / 6.0; // luật toàn phần: chia đều 1/6
        }
        dp = move(nxt);
    }

    double ans = 0;
    for (int s = a; s <= b; s++) ans += dp[s];
    cout << fixed << setprecision(6) << ans << "\n";
}

Mẫu 2 — DP kỳ vọng ngược (kỳ vọng số bước đến đích trên DAG):

// E[u] = kỳ vọng số bước từ u tới đích t. E[t] = 0.
// adj[u] = các cặp (v, p) với p là xác suất đi u -> v.
vector<double> E(n, 0.0);
for (int u : reverse_topo) {           // duyệt theo topo NGƯỢC
    if (u == t) { E[u] = 0; continue; }
    E[u] = 1.0;                        // mỗi bước tốn 1
    for (auto [v, p] : adj[u])
        E[u] += p * E[v];              // cộng kỳ vọng các nhánh con
}
cout << E[s] << "\n";

Mẫu 3 — kết quả dưới dạng phân số modulo $10^{9} + 7$ (dùng cho dicecombo, invprob):

Khi đề yêu cầu in modulo, không được dùng double. Một phân số $a / b$ được biểu diễn bằng $a \cdot b^{- 1} mod p$ , với $b^{- 1}$ là nghịch đảo modular tính bằng định lý Fermat nhỏ ( $b^{- 1} \equiv b^{p - 2}$ ).

const long long MOD = 1e9 + 7;
long long power(long long b, long long e) {     // lũy thừa nhanh
    long long r = 1; b %= MOD;
    while (e > 0) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}
long long inv(long long a) { return power(a, MOD - 2); } // nghịch đảo modular

// Ví dụ dicecombo: dp[s] = số cách (có thứ tự) tung được tổng s
// dp[s] = dp[s-1] + dp[s-2] + ... + dp[s-6]   (mod p), dp[0] = 1
int main() {
    int n; cin >> n;
    vector<long long> dp(n + 1, 0);
    dp[0] = 1;
    for (int s = 1; s <= n; s++)
        for (int f = 1; f <= 6 && f <= s; f++)
            dp[s] = (dp[s] + dp[s - f]) % MOD;
    cout << dp[n] << "\n";
    // Khi xác suất p/q xuất hiện, nhân thêm inv(q) thay vì chia.
}

Độ phức tạp

Phân bố tổng xúc xắc (Mẫu 1): trạng thái là $(i, s)$ với $i \leq n$ và $s \leq 6 n$ ; mỗi trạng thái xét 6 mặt. Thời gian $O (n \cdot 6 n \cdot 6) = O (n^{2})$ , bộ nhớ $O (n)$ nhờ cuộn mảng 1 chiều (chỉ giữ hàng hiện tại). So với liệt kê $6^{n}$ dãy kết quả, đây là cải thiện hàm mũ → đa thức.
DP kỳ vọng trên DAG (Mẫu 2): mỗi đỉnh xử lý một lần, mỗi cạnh duyệt một lần → $O (V + E)$ thời gian, $O (V)$ bộ nhớ cho mảng E. Lý do $O (V + E)$ : topo sort đảm bảo khi tính E[u] thì mọi E[v] kề đã sẵn sàng, không tính lại.
Giải hệ bằng Gauss (khi có chu trình): $n$ trạng thái tạo hệ $n$ phương trình $\Rightarrow O (n^{3})$ thời gian, $O (n^{2})$ bộ nhớ cho ma trận. Đây thường là nút thắt, nên chỉ dùng khi không cô lập được biến bằng đại số.
Nghịch đảo modular (Mẫu 3): mỗi lần $O (\log p)$ do lũy thừa nhanh; nếu cần nhiều nghịch đảo, tiền xử lý bảng giai thừa nghịch đảo trong $O (n)$ .

⚠️ Lỗi thường gặp

Dùng double cho bài yêu cầu modulo. Triệu chứng: WA dù logic đúng, vì $10^{9} + 7$ không phải phép chia số thực. Cách tránh: biểu diễn mọi phân số bằng nghịch đảo modular ( $a \cdot inv (b) mod p$ ), không bao giờ dùng toán tử / trên số nguyên modulo.
Modulo âm. Khi công thức có phép trừ (ví dụ $1 - p$ dạng modulo), kết quả (a - b) % MOD có thể âm. Cách tránh: viết ((a - b) % MOD + MOD) % MOD.
Sai chiều DP với chu trình. Nếu trạng thái phụ thuộc lẫn nhau (như "thử lại": $E [i] = 1 + p E [i] + (1 - p) E [i + 1]$ ) mà bạn cứ tính tiến, sẽ đọc một biến chưa xác định và lặp vô hạn hoặc ra số rác. Cách tránh: cô lập biến — chuyển $E [i]$ về một vế: $E [i] = \frac{1 + (1 - p) E [i + 1]}{1 - p}$ ; nếu không cô lập được thì dùng Gauss.
Off-by-one ở biên trạng thái. Tổng của $i$ xúc xắc chỉ nằm trong $[i, 6 i]$ ; duyệt $s$ ngoài khoảng này gây cộng nhầm dp rỗng hoặc truy cập âm dp[s-f] khi $s < f$ . Cách tránh: chặn f <= s và giới hạn vòng s đúng biên.
Quên khởi tạo trạng thái đáy. Thiếu dp[0] = 1 (xác suất "chưa làm gì" = 1) hoặc E[đích] = 0 khiến toàn bộ bảng bằng 0. Cách tránh: luôn xác định rõ trạng thái cơ sở trước khi lặp.
Tràn số khi đếm cách không modulo kịp. Với bài đếm (dicecombo), số cách lớn rất nhanh; quên % MOD trong vòng lặp gây tràn long long. Cách tránh: lấy modulo ngay sau mỗi phép cộng/nhân.

Biến thể / Mở rộng

$n$ rất lớn (đến $10^{18}$ ): quan hệ truy hồi tuyến tính như đếm cách tung tổng (bài throwdice) không thể lặp $n$ bước. Dùng nhân ma trận + lũy thừa nhanh đưa về $O (k^{3} \log n)$ với $k$ là bậc truy hồi (ở đây $k = 6$ ).
Kỳ vọng + tối ưu hoá: một số bài trộn kỳ vọng với lựa chọn tối ưu (chọn $\leq M$ hành động để cực tiểu kỳ vọng), khi đó trạng thái thêm chiều "đã dùng bao nhiêu lượt", như bài classrm.
Xem thêm các trang liên quan: DP trên đồ thị, DP bitmask.

Bài tập luyện

Tổ Hợp Xúc Xắc (dicecombo) — (Amateur) Đếm số cách (có thứ tự) tung xúc xắc để được tổng $n$ theo modulo — bài nhập môn DP tiến trên tổng kèm nghịch đảo/modulo.
Tung xúc xắc (throwdice) — (Intermediate) Cùng truy hồi đếm tổng nhưng $n$ tới $10^{18}$ , buộc dùng nhân ma trận để tăng tốc — luyện mở rộng truy hồi tuyến tính.
Xác suất xúc xắc (diceprob) — (Advanced) Tính xác suất tổng của $n$ xúc xắc rơi vào đoạn $[a, b]$ — đúng mẫu DP xác suất tiến lan truyền phân bố tổng.
Xác suất nghịch thế (invprob) — (Advanced) Kỳ vọng/xác suất kết hợp tổ hợp, kết quả dạng phân số modulo — luyện biểu diễn xác suất bằng nghịch đảo modular.
Phòng Học Hogwarts (classrm) — (Advanced) Cực tiểu hoá tổng khoảng cách kỳ vọng với giới hạn $M$ đơn xin đổi phòng — kết hợp kỳ vọng, đường đi ngắn nhất trên đồ thị và DP chọn lựa.