นับจำนวนวิธีวางโดมิโนและโตรมิโนเติมพื้นที่ 2×N ใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะนับจำนวนวิธีการปูพื้นที่ 2×N ด้วย:

Domino: ขนาด 2×1 (ตั้งตรง) หรือ 1×2 (นอน)
Tromino: รูปตัว L (3 ช่อง) สามารถหมุนได้ 4 ทิศทาง

ตัวอย่าง

N = 3 → Output: 5

ความสัมพันธ์เวียนเกิด (Recurrence)

ให้ dp[n] = จำนวนวิธีปู 2×n

dp[1] = 1 (1 โดมิโนตั้ง)
dp[2] = 2 (2 โดมิโนตั้ง, หรือ 2 โดมิโนนอน)
dp[3] = 5

สำหรับ n ≥ 4: dp[n] = 2×dp[n-1] + dp[n-3]

เหตุผลของสูตร

2×dp[n-1]: เพิ่มโดมิโนตั้งที่ขวาสุด (2 วิธี: บน/ล่าง)
dp[n-3]: เพิ่มรูปแบบ L-tromino + โดมิโน ที่ครอบ 3 คอลัมน์สุดท้าย

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

#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 solve(int N) {
        vector dp(N + 5, 0);
        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.solve(3);
    return 0;
}

ผลลัพธ์

คำอธิบาย N=3

5 วิธี (อักษรต่าง = กระเบื้องต่าง): XYZ XXZ XYY XXY XYY XYZ YYZ XZZ XYY XXY

สรุป

DP แบบ Linear Recurrence O(N) โจทย์คลาสสิก Tiling with Dominoes and Trominoes (LeetCode 790) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ