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

DP bitmask

huunguyen Updated Tháng sáu 1, 2026

DP bitmask (quy hoạch động trên mặt nạ bit) là kỹ thuật dùng một số nguyên nhị phân để mã hoá trạng thái là một tập con của $n$ phần tử: bit thứ $i$ bằng 1 nghĩa là phần tử $i$ đã được chọn/đã xử lý. Nhờ đó ta có thể xét tất cả $2^{n}$ tập con một cách có hệ thống, đổi bài toán hoán vị $O (n!)$ (ví dụ TSP duyệt mọi thứ tự) thành $O (2^{n} \cdot n^{2})$ — với $n \leq 20$ thì hoàn toàn chạy được.

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

Vì sao bitmask DP đúng? Mấu chốt nằm ở chỗ: với nhiều bài toán "chọn/sắp xếp $n$ phần tử", kết quả tối ưu chỉ phụ thuộc vào TẬP các phần tử đã dùng, không phụ thuộc vào THỨ TỰ ta đã dùng chúng.

Ví dụ trong bài người đưa thư (TSP): nếu ta đã thăm tập thành phố $S$ và hiện đang đứng ở thành phố $u$ , thì chi phí đi tiếp không quan tâm ta đã đi qua $S$ theo thứ tự nào — chỉ cần biết "đã đi những thành phố nào" và "đang ở đâu". Tất cả các thứ tự khác nhau cho cùng $(S, u)$ đều dẫn tới cùng một bài toán con trong tương lai. Đó chính là tính chất chồng lấp bài toán con (overlapping subproblems): thay vì $n!$ thứ tự, ta gộp chúng lại thành $2^{n} \cdot n$ trạng thái $(S, u)$ và chỉ giữ giá trị tốt nhất cho mỗi trạng thái.

Một số nguyên 32-bit thừa sức chứa $n \leq 20$ bit, lại cho phép so sánh, đánh chỉ số mảng và thao tác tập hợp (hợp, giao, thêm phần tử) bằng một phép toán bit duy nhất. Vì vậy "tập con" trở thành "chỉ số mảng" $d p [mask]$ , và ta quy hoạch động trên đó như bình thường.

Điều kiện áp dụng cốt lõi: $n$ nhỏ (thường $n \leq 20$ , hay gặp $n \leq 18$ ), vì không gian trạng thái là $2^{n}$ nhân thêm vài thông tin phụ.

Nhắc lại thao tác bit

mask | (1 << i)          // bật bit i  (thêm phần tử i vào tập)
mask & ~(1 << i)         // tắt bit i  (loại phần tử i)
mask ^ (1 << i)          // đảo bit i
(mask >> i) & 1          // bit i có bật không? (phần tử i có trong tập?)
mask & (mask - 1)        // tắt bit 1 thấp nhất
__builtin_popcount(mask) // đếm số bit 1 (kích thước tập)
(1 << n) - 1             // mask gồm n bit 1 (tập đầy đủ)

Lưu ý: 1 << i là số nguyên int. Nếu cần $n \geq 31$ thì phải viết 1LL << i.

Ví dụ chạy tay: TSP với 3 thành phố

Xét ma trận chi phí cho $n = 3$ thành phố (xuất phát từ 0, đi hết rồi quay về 0):

dist  | tới 0  tới 1  tới 2
------+---------------------
từ 0  |   0     10     15
từ 1  |  10      0     20
từ 2  |  15     20      0

Trạng thái dp[mask][u] = chi phí nhỏ nhất để đi qua đúng tập thành phố mask, kết thúc ở u. Ta điền bảng theo thứ tự mask tăng dần (vì mask lớn luôn nhận chuyển từ mask nhỏ hơn). Ô . nghĩa là $+ \infty$ (chưa với tới được). Mask viết dạng nhị phân, bit 0 là thành phố 0.

Khởi tạo: chỉ dp[001][0] = 0 (đứng ở thành phố 0, mới thăm mình nó).

mask=001 (chỉ {0})
   u=0: dp=0  --> đi tới 1: dp[011][1]=0+10=10
                  đi tới 2: dp[101][2]=0+15=15
mask=011 ({0,1})
 [u=1]: dp=10 --> đi tới 2: dp[111][2]=10+20=30   <-- đang xét
mask=101 ({0,2})
 [u=2]: dp=15 --> đi tới 1: dp[111][1]=15+20=35   <-- đang xét

Bảng dp sau khi điền xong (cột = thành phố kết thúc u):

mask \ u |   0     1     2
---------+-------------------
001      |   0     .     .
011      |   .    10     .
101      |   .     .    15
111      |   .    35   [30]

Cuối cùng cộng chặng quay về 0: $a n s = {min}_{u} (d p [111] [u] + d i s t [u] [0])$

qua $u = 1$ : $35 + d i s t [1] [0] = 35 + 10 = 45$
qua $u = 2$ : $30 + d i s t [2] [0] = 30 + 15 = 45$

Đáp số 45 (chu trình $0 \to 1 \to 2 \to 0 = 10 + 20 + 15$ ). Quan trọng: hai cách đi tới mask=111 đều được gộp về cùng bảng, ta chỉ giữ giá trị tốt nhất cho mỗi cặp $(mask, u)$ .

Cài đặt

TSP (bài toán người đưa thư)

$d p [mask ∣ (1 ≪ v)] [v] = min (d p [mask] [u] + dist [u] [v])$

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];

    const int INF = 1e9;
    int FULL = (1 << n) - 1;
    // dp[mask][u] = chi phí nhỏ nhất, đã đi qua đúng tập mask, đang đứng ở u
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;  // bắt đầu tại thành phố 0, tập mới có {0}

    // Duyệt mask tăng dần: mọi chuyển đều đi từ tập nhỏ sang tập lớn hơn
    for (int mask = 1; mask <= FULL; mask++) {
        for (int u = 0; u < n; u++) {
            if (!((mask >> u) & 1)) continue;   // u phải nằm trong mask
            if (dp[mask][u] == INF) continue;    // trạng thái chưa với tới
            for (int v = 0; v < n; v++) {
                if ((mask >> v) & 1) continue;   // v đã đi rồi thì bỏ qua
                int nm = mask | (1 << v);
                dp[nm][v] = min(dp[nm][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    int ans = INF;
    for (int u = 1; u < n; u++)             // cộng chặng quay về 0
        ans = min(ans, dp[FULL][u] + dist[u][0]);
    cout << ans << "\n";
}

Bài toán phân công (Assignment) — bitmask 1 chiều

Có $n$ người, $n$ việc; người $i$ làm việc $j$ tốn $c [i] [j]$ . Mỗi người một việc, cực tiểu tổng. Mẹo: số người đã phân công chính bằng số bit 1 của mask, nên không cần chiều thứ hai.

vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] == INT_MAX) continue;
    int person = __builtin_popcount(mask); // người tiếp theo cần phân công
    if (person == n) continue;
    for (int job = 0; job < n; job++) {
        if ((mask >> job) & 1) continue;   // việc đã có người nhận
        int nm = mask | (1 << job);
        dp[nm] = min(dp[nm], dp[mask] + c[person][job]);
    }
}
cout << dp[(1 << n) - 1] << "\n";          // mọi việc đã được giao

SOS DP (Sum over Subsets) — tính tổng trên mọi tập con

Cho mảng $a$ kích thước $2^{n}$ . Tính $f [mask] = \sum_{sub \subseteq mask} a [sub]$ . Duyệt trâu là $O (3^{n})$ ; SOS DP hạ xuống $O (n \cdot 2^{n})$ bằng cách "góp" theo từng bit.

vector<long long> f(a.begin(), a.end());
for (int i = 0; i < n; i++)
    for (int mask = 0; mask < (1 << n); mask++)
        if ((mask >> i) & 1)
            f[mask] += f[mask ^ (1 << i)]; // gộp các tập con khác nhau ở bit i

Độ phức tạp

Bài toán	Trạng thái	Thời gian	Bộ nhớ
TSP	`dp[mask][u]`	$O (2^{n} \cdot n^{2})$	$O (2^{n} \cdot n)$
Assignment	`dp[mask]`	$O (2^{n} \cdot n)$	$O (2^{n})$
Lát gạch / broken profile	`dp[i][mask]`	$O (n \cdot 2^{m} \cdot \dots)$	$O (2^{m})$
SOS DP	`f[mask]`	$O (n \cdot 2^{n})$	$O (2^{n})$

Vì sao TSP là $O (2^{n} \cdot n^{2})$ : có $2^{n}$ giá trị mask, mỗi mask xét $n$ điểm kết thúc u, mỗi u thử $n$ điểm tiếp theo v → $2^{n} \cdot n \cdot n$ phép cập nhật. Bộ nhớ $O (2^{n} \cdot n)$ vì lưu một bảng dp có $2^{n}$ hàng và $n$ cột.

Vì sao SOS DP là $O (n \cdot 2^{n})$ : ta lặp $n$ bit, mỗi bit quét hết $2^{n}$ mask một lần, mỗi lần $O (1)$ .

Giới hạn thực tế của $2^{n}$ (mỗi phần tử int ~ 4 byte):

$n$	$2^{n}$	Ghi chú
18	~262K	rất thoải mái
20	~1M	DP bitmask thường OK
22	~4M	cần để ý bộ nhớ
25	~33M	dễ MLE/TLE
30+	~1B	KHÔNG dùng DP bitmask thuần

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

Tràn int khi dịch bit: 1 << i với $i \geq 31$ là hành vi không xác định, và 1 << 31 đã âm. Khi $n$ lớn hoặc cần mask rộng, dùng 1LL << i và kiểu long long. Tương tự, tổng chi phí TSP/đếm số cách có thể vượt int → dùng long long cho dp khi cần.
Quên INF khi cộng dồn: trong TSP, cộng dp[mask][u] + dist[u][v] mà không kiểm tra dp[mask][u] == INF trước sẽ làm INF + dist tràn hoặc lan giá trị rác ra toàn bảng. Luôn continue khi trạng thái nguồn còn là $\infty$ .
Sai thứ tự duyệt mask: công thức chuyển đi từ tập nhỏ sang tập lớn (thêm bit), nên phải duyệt mask tăng dần. Nếu vô tình duyệt giảm dần (hoặc đặt vòng lặp sai), trạng thái nguồn chưa được tính xong đã bị đọc → kết quả sai âm thầm, không báo lỗi.
Nhầm "phần tử $i$ " với "bit thứ $i$ ": chỉ số phần tử và vị trí bit phải nhất quán (đánh số từ 0). Trộn lẫn 1 << (i+1) ở chỗ này, 1 << i ở chỗ khác là lỗi off-by-one kinh điển.
Độ ưu tiên toán tử: mask >> i & 1 đúng, nhưng mask & 1 << i == 0 thì SAI vì == được tính trước <</&. Luôn đóng ngoặc: (mask & (1 << i)) == 0.
Duyệt tập con quên sub = 0: vòng for (int sub = mask; sub > 0; sub = (sub - 1) & mask) không xét tập rỗng sub = 0. Nếu bài cần cả tập rỗng, xử lý riêng.

Biến thể / Mở rộng

Broken profile / lát gạch: khi DP theo từng hàng/ô của bảng, mask mã hoá "đường biên lởm chởm" giữa phần đã lát và chưa lát. Xem trang DP broken profile.
Duyệt mọi tập con của một mask trong $O (3^{n})$ tổng cộng:

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // xử lý sub là tập con khác rỗng của mask
}

Shortest Superstring: ghép $n$ xâu thành xâu ngắn nhất, dp[mask][i] = độ dài nhỏ nhất khi đã ghép tập mask, kết thúc bằng xâu $i$ ; chuyển bằng độ chồng (overlap) lớn nhất giữa hai xâu.
Meet in the middle: khi $n$ tới 30–40, chia đôi tập, làm $2^{n / 2}$ mỗi nửa rồi ghép — thay thế cho bitmask DP thuần.

Bài tập luyện

Xếp chuồng (juststall) — (Apprentice) Bài nhập môn bitmask DP, làm quen biểu diễn tập con và chuyển trạng thái thêm từng phần tử.
Dây Điện Chuồng Bò (haywire) — (Amateur) Tối ưu cách xếp/ghép một số nhỏ đối tượng, luyện dp[mask] cổ điển.
QUIDDITCH Đội Quidditch (quidditch) — (Advanced) Bài phân công (assignment) dùng mẹo popcount(mask) để bỏ chiều thứ hai.
Đếm Cách Lát Gạch (cnttiling) — (Veteran) Đếm số cách phủ bảng bằng DP bitmask theo hàng / broken profile.
Du Lịch Đảo (islandtravel) — (Veteran) Hành trình kiểu TSP dp[mask][u] kết hợp BFS tính khoảng cách giữa các đảo.
Mảnh Ghép Lời Tiên Tri (prophecy) — (Expert) Shortest Superstring: ghép $n$ xâu bằng dp[mask][i] với độ chồng cực đại.