Hiểu bài toán

Bài toán yêu cầu đếm số cách lát một hình chữ nhật có kích thước 3×n bằng các domino 2×1 (hoặc 1×2). Các domino phải lát phủ kín hình chữ nhật, không được chồng lên nhau và không được lòi ra ngoài. Với n là số tự nhiên, n ≤ 31. Do kết quả có thể rất lớn, cần lưu ý kiểu dữ liệu (ví dụ unsigned long long hoặc mảng số lớn).

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming) dựa trên biểu thức toán học

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    // Khởi tạo mảng DP với kích thước 32
    vector<unsigned long long> dp(32, 0);

    // Base cases
    dp[0] = 1; // Hình rỗng có 1 cách lát
    dp[2] = 3; // Ví dụ mẫu cho n=2

    // Công thức truy hồi: f(n) = 4 * f(n-2) - f(n-4)
    // Chỉ tính cho n chẵn, n lẻ mặc định là 0
    for (int i = 4; i <= 31; i += 2) {
        dp[i] = 4 * dp[i - 2] - dp[i - 4];
    }

    while (T--) {
        int n;
        cin >> n;
        cout << dp[n] << "\n";
    }
    return 0;
}

• Time Complexity: O(T + 31) ~ O(1)
• Space Complexity: O(1)

Đây là phương pháp tối ưu nhất dựa trên tính chất toán học của bài toán lát gạch 3xn. Số cách lát thỏa mãn công thức truy hồi: f(n) = 4f(n-2) - f(n-4). Ta có thể precompute (tính trước) các giá trị này vào mảng DP. Base cases: f(0) = 1, f(2) = 3. Với n lẻ, kết quả luôn là 0 vì diện tích 3n lẻ không thể chia hết cho diện tích domino (2).

Cách Quy hoạch động theo trạng thái hàng (State DP)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    // dp[i] là số cách lát đến cột i
    vector<long long> dp(32, 0);
    // f[0] là số cách lát kín cột hiện tại khi xét từ cột trước đó
    vector<long long> f(32, 0);

    dp[0] = 1;
    f[0] = 0;

    for(int i = 2; i <= 31; i += 2) {
        // Công thức suy ra từ tổng quát
        dp[i] = 4 * dp[i-2] - f[i-2];
        f[i] = dp[i-2];
    }

    while(T--) {
        int n;
        cin >> n;
        if (n % 2 != 0) cout << 0 << "\n";
        else cout << dp[n] << "\n";
    }
    return 0;
}

• Time Complexity: O(T + 31)
• Space Complexity: O(1)

Phương pháp này phân tích chi tiết hơn bằng cách sử dụng các hàm phụ. f(n) là số cách lát để lại một khoảng trống hình 'vảy cá' (không thể lát thêm ở cột hiện tại). Tuy nhiên, sau khi đơn giản hóa, ta nhận được chính xác công thức f(n) = 4f(n-2) - f(n-4). Code này là một cách triển khai trực tiếp các suy luận cơ bản nhưng thường được gộp lại thành công thức tối ưu ở Approach 1.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Số cách lát hình 3xn chỉ khác 0 khi n là số chẵn.
• Bài toán tuân theo quy luật toán học nghiêm ngặt: f(n) = 4*f(n-2) - f(n-4) với n chẵn.
• Với n nhỏ (≤ 31), ta có thể precompute toàn bộ kết quả trước khi xử lý các test case để tối ưu thời gian.

Lỗi thường gặp

• Quên xử lý trường hợp n lẻ (kết quả phải là 0).
• Sử dụng kiểu dữ liệu quá nhỏ (như int) dẫn đến tràn số (overflow) vì kết quả tăng rất nhanh (ví dụ f(30) ≈ 1.5 * 10^9). Nên dùng unsigned long long.
• Lỗi công thức: ghi nhầm thành f(n) = 4f(n-1) - f(n-2) (sai) thay vì f(n) = 4f(n-2) - f(n-4).