DP bitmask

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

huunguyen · Last updated 8, Tháng 4, 2026, 17:10

DP bitmask là kỹ thuật quy hoạch động dùng số nguyên nhị phân để biểu diễn 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ắc lại thao tác bit

mask | (1 << i)    // bật bit i
mask & ~(1 << i)   // tắt bit i
mask ^ (1 << i)    // đảo bit i
(mask >> i) & 1    // kiểm tra bit i có bật không
mask & (mask - 1)  // tắt bit 1 thấp nhất
__builtin_popcount(mask) // đếm số bit 1
(1 << n) - 1       // mask có n bit 1 (tập đầy đủ)

Nhận dạng bài toán

$n$ nhỏ ( $n \leq 20$ , thường $n \leq 18$ ).
Cần duyệt/tối ưu qua tất cả tập con của $n$ phần tử.
Thứ tự hoặc sự kết hợp của các phần tử ảnh hưởng đến kết quả.

Không gian trạng thái: $2^{n}$ tập con × các thông tin bổ sung.

Ví dụ 1: Bài toán người đưa thư (TSP)

Bài toán: Xuất phát từ thành phố 0, đi qua tất cả $n$ thành phố đúng một lần và quay về. Tìm hành trình có tổng chi phí nhỏ nhất.

Trạng thái: dp[mask][u] = chi phí nhỏ nhất để đi qua đúng các thành phố trong mask, kết thúc tại thành phố u.

Công thức chuyển:

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í thấp nhất, đã đi qua tập mask, đang ở u
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;  // bắt đầu tại thành phố 0

    for (int mask = 1; mask <= FULL; mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == INF) continue;
            if (!((mask >> u) & 1)) continue;
            for (int v = 0; v < n; v++) {
                if ((mask >> v) & 1) continue;  // v đã đi rồi
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    int ans = INF;
    for (int u = 1; u < n; u++)
        ans = min(ans, dp[FULL][u] + dist[u][0]);
    cout << ans << "\n";
}

Độ phức tạp: $O (2^{n} \cdot n^{2})$ thời gian, $O (2^{n} \cdot n)$ bộ nhớ.

Ví dụ 2: Phân công công việc (Assignment Problem)

Bài toán: Có $n$ người và $n$ công việc. Người $i$ làm công việc $j$ mất $c [i] [j]$ thời gian. Phân công mỗi người đúng một việc để tổng thời gian nhỏ nhất.

Trạng thái: dp[mask] = chi phí nhỏ nhất khi đã phân công cho $popcount (mask)$ người đầu tiên, và mask biểu diễn tập công việc đã được nhận.

int n;
vector<vector<int>> c(n, vector<int>(n));
// ... đọc input

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 làm
        dp[mask | (1 << job)] = min(dp[mask | (1 << job)], dp[mask] + c[person][job]);
    }
}
cout << dp[(1 << n) - 1] << "\n";

Ví dụ 3: Đếm số cách phủ bảng

Bài toán: Cho bảng $n \times m$ ( $m \leq 20$ ), đặt các ô theo hàng, mỗi ô có thể bật/tắt. Đếm số cách điền sao cho không có hai ô 1 liền kề theo hàng.

Trạng thái: dp[i][mask] = số cách điền $i$ hàng đầu, hàng $i$ có trạng thái mask.

// Kiểm tra mask hợp lệ: không có hai bit 1 liền nhau
auto valid = [](int mask) {
    return (mask & (mask >> 1)) == 0;
};

vector<vector<long long>> dp(n + 1, vector<long long>(1 << m, 0));
// Hàng 0: mọi mask hợp lệ đều được
for (int mask = 0; mask < (1 << m); mask++)
    if (valid(mask)) dp[0][mask] = 1;

for (int i = 1; i < n; i++) {
    for (int cur = 0; cur < (1 << m); cur++) {
        if (!valid(cur)) continue;
        for (int prev = 0; prev < (1 << m); prev++) {
            if (!valid(prev)) continue;
            if (cur & prev) continue;  // hai hàng liền nhau không cùng bật ô
            dp[i][cur] += dp[i-1][prev];
        }
    }
}

long long ans = 0;
for (int mask = 0; mask < (1 << m); mask++)
    ans += dp[n-1][mask];
cout << ans << "\n";

Ví dụ 4: SOS DP (Sum over Subsets)

Bài toán: Cho mảng $a$ có $2^{n}$ phần tử. Tính $f [mask] = \sum_{sub \subseteq mask} a [sub]$ cho mọi mask.

Duyệt trâu mọi tập con: $O (3^{n})$ . Dùng SOS DP: $O (n \cdot 2^{n})$ .

// f[mask] = tổng a[sub] cho mọi sub là tập con của mask
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)];
        }
    }
}

Ứng dụng: Bài toán AND/OR convolution, counting pairs với AND/OR/XOR constraints.

Mẹo thực chiến

Duyệt tất cả tập con của mask

// Cách 1: O(2^n) cho mỗi mask → O(3^n) tổng
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // xử lý sub
}
// Lưu ý: vòng lặp này không xét sub = 0, thêm riêng nếu cần

// Cách 2: dùng SOS DP nếu cần tổng/min/max

Giới hạn thực tế

$n$	$2^{n}$	Ghi chú
20	~1M	DP bitmask thường OK
22	~4M	Cần tối ưu bộ nhớ
25	~33M	Khả năng bị MLE
30+	~1B	Không dùng DP bitmask

Khởi tạo mảng lớn

// Dùng fill thay vì memset với giá trị không phải 0/-1
fill(dp.begin(), dp.end(), vector<int>(n, INF));

Ví dụ 5: Xâu siêu ngắn nhất (Shortest Superstring)

Bài toán: Cho $n$ xâu ( $n \leq 18$ ), tìm xâu ngắn nhất chứa tất cả các xâu đó làm xâu con liên tiếp.

Tiền xử lý:

Loại bỏ các xâu là substring của xâu khác (chúng đã được "bao" miễn phí).
Tính sẵn over[i][j] = độ dài suffix lớn nhất của $s_{i}$ khớp với prefix của $s_{j}$ .

Trạng thái: dp[mask][i] = độ dài nhỏ nhất của xâu ghép từ tập mask, kết thúc bằng $s_{i}$ .

Transition:

d p [mask \cup {j}] [j] = min (d p [mask] [i] + | s_{j} | - over [i] [j])

Khi ghép $s_{j}$ sau $s_{i}$ , phần overlap dài over[i][j] được tính chung → chỉ cần thêm |s_j| - over[i][j] ký tự mới.

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

// Độ dài suffix của a khớp với prefix của b
int overlap(const string& a, const string& b) {
    int la = a.size(), lb = b.size();
    for (int k = min(la, lb); k >= 1; k--)
        if (a.substr(la - k) == b.substr(0, k)) return k;
    return 0;
}

int main() {
    int n; cin >> n;
    vector<string> s(n);
    for (auto& x : s) cin >> x;

    // Loại xâu trùng và xâu là substring của xâu khác
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    vector<string> t;
    for (int i = 0; i < (int)s.size(); i++) {
        bool sub = false;
        for (int j = 0; j < (int)s.size(); j++)
            if (i != j && s[j].find(s[i]) != string::npos) { sub = true; break; }
        if (!sub) t.push_back(s[i]);
    }
    s = t; n = s.size();

    // Tính overlap
    vector<vector<int>> ov(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j) ov[i][j] = overlap(s[i], s[j]);

    // DP bitmask
    const int INF = 1e9;
    int FULL = 1 << n;
    vector<vector<int>> dp(FULL, vector<int>(n, INF));
    for (int i = 0; i < n; i++) dp[1 << i][i] = s[i].size();

    for (int mask = 0; mask < FULL; mask++)
        for (int i = 0; i < n; i++) if (dp[mask][i] < INF)
            for (int j = 0; j < n; j++) if (!(mask >> j & 1))
                dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
                                              dp[mask][i] + (int)s[j].size() - ov[i][j]);

    int ans = INF;
    for (int i = 0; i < n; i++) ans = min(ans, dp[FULL - 1][i]);
    cout << ans << "\n";
}

Độ phức tạp: $O (n^{2} \cdot 2^{n})$ thời gian, $O (n \cdot 2^{n})$ bộ nhớ.

Bài tập minh họa: Mảnh Ghép Lời Tiên Tri (prophecy) — Tìm xâu ngắn nhất chứa tất cả $n$ mảnh ghép cho trước.

Tổng kết các bài toán DP bitmask thường gặp

Bài toán	Trạng thái	Độ phức tạp
TSP	`dp[mask][u]`	$O (2^{n} n^{2})$
Assignment	`dp[mask]`	$O (2^{n} n)$
Covering set	`dp[mask]`	$O (2^{n} n)$
Broken profile	`dp[i][mask]`	$O (n \cdot m \cdot 2^{m})$
SOS DP	`f[mask]`	$O (n \cdot 2^{n})$
Shortest Superstring	`dp[mask][i]`	$O (2^{n} n^{2})$

Bình luận

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