การปูกระเบื้องโดมิโนและท्रोมิโนใน C++

มีกระเบื้อง 2 ประเภท: โดมิโน (Domino) ขนาด 2×1 และ โทรมิโน (Tromino) รูปตัว L (ครอบ 3 ช่อง) สามารถหมุนได้ ทุกช่องบนกระดาน 2×N ต้องถูกปูครบ ทางปูต่างกันก็ต่อเมื่อมีช่องติดกัน 2 ช่องที่ปูต่างกัน

ตัวอย่าง: N=3 → 5 วิธี

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. สร้างอาร์เรย์ dp[N+5]
2. ฐาน: dp[1]=1, dp[2]=2, dp[3]=5
3. สัมพันธ์เวียนเกิด: dp[i] = 2*dp[i-1] + dp[i-3] สำหรับ i >= 4
4. คำตอบ = dp[N] (mod 1e9+7)

เหตุผล: พิจารณาคอลัมน์สุดท้าย — เป็นโดมิโนตั้ง (dp[i-1]), โดมิโนนอนคู่ (dp[i-2]), หรือโทรมิโนร่วมกับคอลัมน์ก่อนหน้า (dp[i-3] × 2 แบบ)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b) { return ((a%MOD) + (b%MOD)) % MOD; }

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

int main() {
    Solution ob;
    cout << ob.numTilings(3);
}

Input

3

Output

5