DP broken profile

DP broken profile (quy hoạch động theo "đường biên gãy") là kỹ thuật DP dùng bitmask để lấp đầy một lưới ô vuông $n\times m$ theo từng ô một (thay vì từng cột nguyên khối). Nó giải các bài toán đếm/tối ưu cách lát gạch, tô màu lưới, đặt vật trên lưới với độ phức tạp $O(n·m·2^m)$ — nhanh hơn nhiều so với liệt kê toàn bộ cấu hình $O(2^{nm})$ một cách ngây thơ.

Ý tưởng cốt lõi: khi duyệt lưới theo thứ tự ô-một, tại mỗi thời điểm ta chỉ cần biết trạng thái của $m$ ô nằm trên "đường biên" giữa phần đã xử lý và phần chưa xử lý. $m$ ô đó được mã hoá bằng một bitmask $m$ bit, nên số trạng thái chỉ là $2^m$.

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

Hãy hình dung ta lấp lưới theo thứ tự đọc sách: hàng 0 từ trái sang phải, rồi hàng 1, ... Tại một thời điểm bất kỳ, "biên giới" giữa vùng đã quyết định và vùng chưa quyết định không phải một đường thẳng, mà là một đường gấp khúc (broken profile): vài ô của hàng hiện tại đã xử lý, vài ô của hàng trên vẫn còn ảnh hưởng xuống.

Câu hỏi mấu chốt: để điền tiếp các ô còn lại, ta cần nhớ gì về quá khứ? Câu trả lời: chỉ cần biết, trong số $m$ ô nằm ngay trên đường biên, ô nào đã bị một viên gạch trước đó chiếm chỗ (sẽ "thò" xuống), ô nào còn trống. Mọi chi tiết khác của quá khứ (gạch đặt thế nào ở các hàng phía trên) không ảnh hưởng tới cách lấp phần còn lại. Đây chính là tính chất Markov khiến DP áp dụng được.

Vì đường biên đúng bằng $m$ ô liên tiếp nên ta mã hoá nó bằng bitmask $m$ bit:

• bit $=1$: ô tương ứng đã bị chiếm (bởi gạch đặt từ ô trước/hàng trên).
• bit $=0$: ô tương ứng còn trống, cần được lấp.

Khi xử lý ô $(i,j)$, ta đọc bit ứng với ô đó: nếu đã bị chiếm thì chỉ việc "trượt" biên qua; nếu còn trống thì thử mọi cách đặt gạch phủ ô này. Mỗi lựa chọn sinh ra một bitmask mới cho bước kế tiếp. Tổng số cách = tổng các đường đi hợp lệ trong đồ thị trạng thái này.

So với DP bitmask theo cột (chuyển cả cột một lúc, phải liệt kê mọi cặp mask hợp lệ giữa hai cột), broken profile chuyển từng ô, nên logic chuyển trạng thái đơn giản hơn (mỗi bước chỉ vài lựa chọn), dễ mở rộng cho gạch hình dạng lạ, và tránh phải tiền tính bảng tương thích cột.

Ví dụ chạy tay

Bài toán: đếm số cách lát kín lưới $2\times 2$ bằng domino $1\times 2$ và $2\times 1$ (đáp số đúng là 2: hai domino ngang, hoặc hai domino dọc).

Quy ước: ta duyệt ô theo thứ tự $(0,0),(0,1),(1,0),(1,1)$. Bitmask có $m=2$ bit; bit $j$ ứng với cột $j$ của "đường biên hiện tại". Khi đứng ở ô $(i,j)$:

• bit $j$ = trạng thái của chính ô $(i,j)$ (đã bị gạch dọc từ hàng trên phủ chưa).
• các bit $>j$ ứng với các ô còn lại của hàng $i$; các bit $<j$ ứng với các ô của hàng $i+1$ (đã được gạch dọc "đặt trước").

Khởi tạo: dp[00] = 1 (chưa điền gì, biên trống trơn).

Lưới 2x2, ô đang xét đánh dấu [ ]:

Bước (0,0):  Bước (0,1):  Bước (1,0):  Bước (1,1):
 [.] .         x  [.]       [?] .        x  [?]
  .  .          .  .         ?  .         ?  .

Xét ô $(0,0)$, mask 00 (bit0=ô(0,0), bit1=ô(0,1)):

• ô trống. Đặt gạch dọc phủ $(0,0),(1,0)$: đánh dấu ô $(1,0)$ sẽ bị chiếm. Sang ô kế, mask thành 01 (bit ô (0,0) tắt khi trượt qua, nhưng ô(1,0) được ghi). Để gọn, ta dùng quy ước mask đại diện "các ô của biên kế tiếp": kết quả dp'[10] += 1.
• Đặt gạch ngang phủ $(0,0),(0,1)$: cả hai ô hàng 0 bị chiếm: dp'[01] += 1 (ô (0,1) đánh dấu chiếm).

Sau bước $(0,0)$:

Xét ô $(0,1)$:

• Từ mask 10 (ô (0,1) trống): chỉ còn cách đặt gạch dọc phủ $(0,1),(1,1)$ → đánh dấu ô (1,1). Sang hàng 1, mask 11 (cả (1,0),(1,1) bị chiếm).
• Từ mask 01 (ô (0,1) đã bị chiếm): chỉ trượt qua, hàng 1 hoàn toàn trống → mask 00.

Sang hàng 1:

Xét ô $(1,0)$ rồi $(1,1)$:

• Nhánh 11: cả hai ô hàng 1 đã bị chiếm sẵn → chỉ trượt qua, không đặt gì → về 00. Hợp lệ (đây là phương án "hai gạch dọc").
• Nhánh 00: ô (1,0) trống, đặt gạch ngang phủ $(1,0),(1,1)$ → cả hai bị chiếm → kết thúc về 00. Hợp lệ (phương án "hai gạch ngang"). (Đặt gạch dọc ở (1,0) sẽ thò ra ngoài lưới nên bị loại.)

Kết quả cuối: dp[00] = 2. Đúng bằng 2 cách lát mong đợi. Bảng DP đã "thấy" rõ hai đường đi tương ứng hai cấu hình.

Cài đặt

Cài đặt chuẩn cho bài đếm cách lát domino $1\times 2$ / $2\times 1$ lưới $n\times m$ (lấy $m$ là chiều nhỏ), kết quả modulo ${10}^9+7$:

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

const long long MOD = 1e9 + 7;

int n, m;

int main() {
    cin >> n >> m;
    if (m > n) swap(n, m); // luôn để m là chiều nhỏ -> 2^m nhỏ nhất

    // dp[mask]: số cách điền tới ô hiện tại, mask = trạng thái m ô của biên gãy.
    // bit = 1 nghĩa ô tương ứng đã bị một viên gạch chiếm trước đó.
    vector<long long> dp(1 << m, 0);
    dp[0] = 1; // biên hoàn toàn trống

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            vector<long long> ndp(1 << m, 0);
            for (int mask = 0; mask < (1 << m); mask++) {
                if (!dp[mask]) continue;

                if (mask & (1 << j)) {
                    // Ô (i,j) đã bị chiếm (bởi gạch dọc từ hàng trên):
                    // chỉ trượt biên qua, xoá bit j cho bước kế tiếp.
                    int nm = mask ^ (1 << j);
                    ndp[nm] = (ndp[nm] + dp[mask]) % MOD;
                } else {
                    // Ô (i,j) trống, bắt buộc phải phủ nó.

                    // 1) Gạch dọc 2x1: phủ (i,j) và (i+1,j).
                    //    Đánh dấu bit j (ô (i+1,j) sẽ bị chiếm ở hàng sau).
                    if (i + 1 < n) {
                        int nm = mask | (1 << j);
                        ndp[nm] = (ndp[nm] + dp[mask]) % MOD;
                    }

                    // 2) Gạch ngang 1x2: phủ (i,j) và (i,j+1).
                    //    Yêu cầu ô (i,j+1) còn trống (bit j+1 = 0).
                    if (j + 1 < m && !(mask & (1 << (j + 1)))) {
                        int nm = mask | (1 << (j + 1)); // ô (i,j+1) bị chiếm
                        ndp[nm] = (ndp[nm] + dp[mask]) % MOD;
                    }
                }
            }
            dp = move(ndp);
        }
    }

    // Sau khi đi hết lưới, đáp án là dp[0]:
    // không ô nào "thò" ra ngoài, mọi ô đã được lấp khít.
    cout << dp[0] << "\n";
    return 0;
}

Mở rộng thêm loại gạch chỉ cần thêm nhánh trong khối "ô trống". Ví dụ gạch $2\times 2$ phủ $(i,j),(i,j+1),(i+1,j),(i+1,j+1)$:

// (đặt cùng chỗ với các nhánh đặt gạch, khi ô (i,j) trống)
if (i + 1 < n && j + 1 < m && !(mask & (1 << (j + 1)))) {
    int nm = mask | (1 << j) | (1 << (j + 1)); // hai ô hàng dưới bị chiếm
    ndp[nm] = (ndp[nm] + dp[mask]) % MOD;
}

Với lưới có ô cấm blocked[i][j]: nếu ô bị cấm thì nó không được đặt gạch và cũng không được bị gạch khác phủ — chỉ cho phép chuyển khi bit j == 0 rồi trượt qua (giữ bit j = 0).

Độ phức tạp

Lý giải thời gian: vòng ngoài chạy đúng số ô $n·m$; với mỗi ô, vòng mask quét $2^m$ trạng thái và mỗi trạng thái sinh ra nhiều nhất 2–3 chuyển trạng thái hằng số. Nhân lại đúng bằng $O(n·m·2^m)$.

Về bộ nhớ: ta luôn chỉ cần trạng thái biên hiện tại và kế tiếp, nên không lưu toàn bộ lịch sử — chỉ $O(2^m)$. Giới hạn thực tế thường là $m\le 12$ vì $2^{12}=4096$ (khi đó $n·m·2^m$ vẫn vừa thời gian); luôn xoay lưới để $m$ là chiều nhỏ hơn.

Khi $n$ cực lớn nhưng $m$ rất nhỏ (ví dụ $m\le 6$), có thể gộp mỗi hàng thành một ma trận chuyển $2^m\times 2^m$ rồi dùng lũy thừa ma trận để đạt $O(2^{3m}\log n)$.

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

• Quên modulo / tràn số. Khi đếm cách lát, kết quả tăng theo cấp số nhân; phải cộng dồn vào long long và lấy % MOD ngay sau mỗi phép cộng. Để int sẽ tràn âm thầm và cho đáp án sai mà không lỗi runtime.
• Sai định nghĩa bit tại ô đang xét. Phải nhất quán: bit $j$ luôn ứng với chính ô $(i,j)$ đang xét. Nếu lúc thì coi bit $j$ là ô hàng trên, lúc thì ô hàng hiện tại, toàn bộ chuyển trạng thái sẽ lệch. Hãy chốt một quy ước (như trong code) và bám sát.
• Đặt gạch thò ra ngoài lưới (off-by-one biên). Gạch dọc chỉ hợp lệ khi i + 1 < n; gạch ngang chỉ khi j + 1 < m. Bỏ kiểm tra này sẽ đếm cả cấu hình vượt biên → đáp án lớn hơn thực tế.
• Quên điều kiện ô kế còn trống khi đặt gạch ngang. Đặt gạch ngang phủ $(i,j),(i,j+1)$ chỉ hợp lệ khi bit $j+1$ đang là 0. Nếu ô $(i,j+1)$ đã bị gạch dọc từ hàng trên chiếm, đặt thêm gạch ngang là chồng gạch — phải loại bằng !(mask & (1 << (j+1))).
• Lấy sai trạng thái kết thúc. Đáp án là dp[0] sau khi đi hết toàn bộ ô, nghĩa là không ô nào còn "thò" sang ngoài. Lấy dp[mask] với mask != 0, hoặc đọc đáp án giữa chừng, đều sai.
• Không xoay lưới khi $m>n$. $2^m$ là yếu tố quyết định tốc độ/bộ nhớ; quên swap để $m$ là chiều nhỏ có thể khiến $2^m$ nổ (ví dụ lưới $2\times 30$ mà lấy $m=30$).
• Sửa dp ngay trong khi đang duyệt. Phải ghi kết quả vào mảng mới ndp rồi mới gán lại; cập nhật tại chỗ sẽ trộn lẫn trạng thái cũ và mới của cùng một bước.

Biến thể / Mở rộng

• Tô màu / gán nhãn lưới với ràng buộc lân cận (số màu nhỏ): broken profile mang theo màu của các ô biên thay vì 1 bit, trạng thái thành $K^m$ (ví dụ bài tối thiểu hoá độ bất hoà âm khi $K$ và $m$ nhỏ).
• Profile nhiều hàng cho gạch hình L, T, hoặc gạch cao hơn 2 ô — biên cần nhớ 2+ hàng.
• Broken profile + lũy thừa ma trận khi $n$ rất lớn, $m$ rất nhỏ.
• Liên hệ với DP bitmask (chuyển theo cột) và DP trên cây khi cấu trúc không phải lưới.

Bài tập luyện

• Domino trên lưới (gridomi) — (Advanced) Lưới có ô cấm #; làm quen mô hình "đặt domino trên lưới ô vuông có ô bị chặn" trước khi đi vào đếm cấu hình bằng broken profile.
• Đếm Cách Lát Gạch (cnttiling) — (Veteran) Bài kinh điển đúng chuẩn broken profile: đếm số cách lát kín lưới — áp dụng trực tiếp cài đặt ở trên.
• Đội Hợp Xướng Hogwarts (choirform) — (Veteran) Profile DP dạng tối ưu: gán mỗi ô một trong $K$ loại giọng để tối thiểu hoá tổng "bất hoà âm" giữa các ô kề; biên mang theo màu của hàng, mở rộng broken profile sang bài tô màu lưới.