Đổ domino và tromino 2xN trong C++

Mô tả bài toán

Đếm số cách đắp bảng 2×N bằng domino (2×1) và tromino (hình L 3 ô). Các ô phải được phủ kín, hai cách đắp khác nhau nếu có cặp ô liền kề 4 hướng mà một cách có cả hai ô được phủ bởi cùng một khối, cách kia không.

Ví dụ: N=3 → 5 cách.

Giải thuật Quy hoạch động

Công thức truy hồi: dp[n] = 2*dp[n-1] + dp[n-3] với dp[1]=1, dp[2]=2, dp[3]=5.

Giải thích: Xét cột cuối cùng, có 2 trường hợp chính dẫn đến truy hồi này (xem chi tiết trong bài giải LeetCode 790).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

class Solution {
public:
    int numTilings(int N) {
        if (N <= 2) return N;
        vector<long long> dp(N+1);
        dp[1] = 1; dp[2] = 2; dp[3] = 5;
        for (int i = 4; i <= N; i++) {
            dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD;
        }
        return dp[N];
    }
};

int main() {
    Solution ob;
    cout << ob.numTilings(3); // 5
    return 0;
}

Độ phức tạp

• Thời gian: O(N).
• Không gian: O(N) (có thể O(1) chỉ lưu 3 giá trị gần nhất).