DP broken profile

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

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

DP broken profile là kỹ thuật DP dùng bitmask để điền lưới ô vuông theo từng ô một (thay vì theo từng cột), cho phép xử lý các bài toán lát gạch với độ phức tạp $O (n \cdot m \cdot 2^{m})$ .

So sánh với DP bitmask thông thường

	DP bitmask theo cột	DP broken profile
Đơn vị chuyển	Cả cột	Từng ô
Trạng thái	Cột hiện tại và cột trước	"Đường biên" gãy giữa hai cột
Ưu điểm	Đơn giản hơn	Tiết kiệm bộ nhớ, xử lý được nhiều dạng gạch hơn
Khi dùng	Gạch $1 \times 2$ hoặc $2 \times 1$	Gạch L, gạch $1 \times k$ , hoặc khi $m$ lớn hơn

Ý tưởng

Duyệt lưới từ trái sang phải, trên xuống dưới theo từng ô $(i, j)$ . Tại mỗi ô, trạng thái bitmask biểu diễn đường biên gãy (broken profile): $m$ bit tương ứng với $m$ ô ngay trên/bên trái vị trí hiện tại.

Ví dụ lưới 3×4, đang xét ô (1,2):
┌─┬─┬─┬─┐
│ █ █ * │  ← hàng 0: đã điền xong
├─┼─┼─┼─┤
│ █ ? │ │  ← ô (1,1) đã điền, ô (1,2) đang xét
├─┼─┼─┼─┤
│ │ │ │ │
└─┴─┴─┴─┘

Broken profile tại (1,2):
bit 0 = ô (1,2) [cùng hàng, cột hiện tại - chính là ô đang xét]
bit 1 = ô (1,3)
bit 2 = ô (0,3) → phần "gãy" sang hàng trên

Ví dụ 1: Lát gạch domino $1 \times 2$ và $2 \times 1$

Bài toán: Đếm số cách lát kín lưới $n \times m$ bằng các gạch domino ( $1 \times 2$ hoặc $2 \times 1$ ). In kết quả modulo $10^{9} + 7$ .

Định nghĩa trạng thái

dp[mask] = số cách lát các ô từ đầu đến ô $(i, j)$ (không tính), với mask là trạng thái $m$ ô của broken profile.

Bit $k = 1$ : ô tương ứng trong profile đã bị chiếm bởi gạch trước đó.
Bit $k = 0$ : ô tương ứng còn trống.

Cài đặt

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

const long long MOD = 1e9 + 7;

int n, m;
long long dp[1 << 12]; // m <= 12

int main() {
    cin >> n >> m;

    // dp[mask]: số cách điền đến vị trí hiện tại
    // mask: m bit biểu diễn trạng thái cột hiện tại và phần đầu cột kế
    fill(dp, dp + (1 << m), 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long ndp[1 << m];
            fill(ndp, ndp + (1 << m), 0);

            for (int mask = 0; mask < (1 << m); mask++) {
                if (!dp[mask]) continue;
                bool cur_filled = (mask >> j) & 1;

                if (cur_filled) {
                    // Ô (i,j) đã được lấp, bỏ qua bit j, chuyển sang ô tiếp
                    ndp[mask ^ (1 << j)] += dp[mask];
                    ndp[mask ^ (1 << j)] %= MOD;
                } else {
                    // Ô (i,j) trống, thử đặt gạch

                    // 1. Đặt gạch dọc (2×1): chiếm (i,j) và (i+1,j)
                    if (i + 1 < n) {
                        ndp[mask | (1 << j)] += dp[mask];
                        ndp[mask | (1 << j)] %= MOD;
                    }

                    // 2. Đặt gạch ngang (1×2): chiếm (i,j) và (i,j+1)
                    if (j + 1 < m && !((mask >> (j + 1)) & 1)) {
                        ndp[mask | (1 << (j + 1))] += dp[mask];
                        ndp[mask | (1 << (j + 1))] %= MOD;
                    }
                }
            }
            copy(ndp, ndp + (1 << m), dp);
        }
    }

    cout << dp[0] << "\n"; // dp[0]: tất cả ô đã được lấp
}

Ví dụ 2: Lát gạch $1 \times 1$ và $2 \times 2$

Thêm tùy chọn đặt gạch $2 \times 2$ — chiếm 4 ô cùng lúc.

// Khi đang ở (i, j), thêm case:
// 3. Đặt gạch 2×2: chiếm (i,j), (i,j+1), (i+1,j), (i+1,j+1)
if (i + 1 < n && j + 1 < m
    && !((mask >> (j+1)) & 1)) {
    // Đánh dấu (i+1,j) và (i+1,j+1) sẽ bị chiếm ở hàng sau
    int newMask = mask | (1 << j) | (1 << (j+1));
    ndp[newMask] += dp[mask];
    ndp[newMask] %= MOD;
}
// 4. Để trống (1×1 tile)
ndp[mask] += dp[mask]; // không đặt gạch nào, ô đơn

Ví dụ 3: Lưới có ô bị chặn

Một số ô trong lưới không thể đặt gạch. Đọc trước bản đồ lưới, bỏ qua ô bị chặn.

bool blocked[105][105];
// Đọc bản đồ blocked[][]

// Trong vòng lặp, khi đến ô (i, j):
if (blocked[i][j]) {
    // Ô này không được đặt gạch, phải để trống
    // Nếu bit j đang bị chiếm (do gạch từ hàng trước): trạng thái không hợp lệ
    for (int mask = 0; mask < (1 << m); mask++) {
        if (!dp[mask]) continue;
        bool cur = (mask >> j) & 1;
        if (cur) continue; // ô bị chặn không thể bị chiếm
        ndp[mask] += dp[mask]; // chỉ "bỏ qua" ô này
        ndp[mask] %= MOD;
    }
}

Độ phức tạp


Thời gian	$O (n \cdot m \cdot 2^{m})$
Không gian	$O (2^{m})$ (chỉ cần 2 mảng dp)

Giới hạn thực tế: $m \leq 12$ (vì $2^{12} = 4096$ ), $n$ có thể lớn hơn.

Nếu $n < m$ : hoán đổi hàng/cột để $m$ là chiều nhỏ hơn.

Mẹo & Lưu ý

Chọn $m$ là chiều nhỏ hơn của lưới để giảm $2^{m}$ .
Kết thúc khi profile mask = 0: nghĩa là không có ô nào "thòi" sang cột tiếp theo.
Với gạch phức tạp hơn (L-shape, T-shape): mở rộng bitmask để theo dõi nhiều hàng hơn, hoặc dùng profile gồm 2 hàng.
Kỹ thuật này thường đi kèm với matrix exponentiation khi $n$ rất lớn nhưng $m$ nhỏ — xây ma trận chuyển $2^{m} \times 2^{m}$ rồi lũy thừa.

Bài toán kinh điển

Bài toán	Gạch
Lát lưới $n \times m$	Domino $1 \times 2$
Đặt quân cờ (non-attacking)	$1 \times 1$ với ràng buộc
Lát lưới có ô chặn	Domino + blocked cells
Lát lưới bằng L-tromino	Gạch L-shape
Lưới $n$ rất lớn, $m \leq 6$	Broken profile + Matrix Exponentiation

Bình luận

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