ข้อ 62 · LC790 Domino and Tromino Tiling (ปูกระเบื้องโดมิโน) 🟡

โจทย์ (LC790): มี tile (กระเบื้อง) สองแบบ ได้แก่ domino (โดมิโน) ขนาด 2 x 1 และ tromino (โทรมิโน) รูปตัว L ซึ่งทั้งสองแบบ rotate (หมุน) ได้ กำหนดจำนวนเต็ม n มา ให้หาจำนวนวิธีปู board (กระดาน) ขนาด 2 x n ทั้งหมด (คำตอบอาจมีขนาดใหญ่มาก ให้ตอบเป็นเศษจากการหารด้วย 10^9 + 7) การปูสองแบบจะถือว่าต่างกันก็ต่อเมื่อมีคู่ช่องที่ติดกันแบบ 4 ทิศคู่ใดคู่หนึ่ง ที่การปูแบบหนึ่งมี tile ปิดครบทั้งคู่ แต่อีกแบบไม่ครบ

แนวทาง — ต้องใช้อะไร & คิดยังไง

โจทย์นี้เป็น DP 1 มิติ (state = จำนวน column ที่ปูเสร็จ) แต่ transition หายากด้วยการมองตรง ๆ เพราะการวาง tromino ทำให้เกิดขอบหยัก ต้อง analyze (วิเคราะห์) กรณีปิด column สุดท้ายอย่างละเอียด ผลลัพธ์ยุบลงมาเป็น recurrence ลัดที่ prove (พิสูจน์) ได้: dp[n] = 2 * dp[n-1] + dp[n-3]

state คือ dp[i] = จำนวนวิธีปู board 2 x i ให้เต็มพอดี base case คือ dp[0] = 1 (board ว่างมีหนึ่งวิธีคือไม่ทำอะไร), dp[1] = 1, dp[2] = 2 ในทางปฏิบัติเรามักจำ recurrence นี้ไว้เลยเพราะ proof (การพิสูจน์) เต็ม ๆ ค่อนข้างยาว

1. define MOD = 10**9 + 7
2. ดัก n <= 2 return n ตรง ๆ (n=1 → 1, n=2 → 2)
3. initialize dp ยาว n+1 ตั้ง dp[0], dp[1], dp[2] = 1, 1, 2
4. iterate i จาก 3 ถึง n: dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD
5. return dp[n]

ไล่ทีละสเต็ป

ไล่จนถึง n = 4 ด้วย recurrence dp[i] = 2*dp[i-1] + dp[i-3]:

def num_tilings(n):
    MOD = 10**9 + 7
    if n <= 2:
        return n          # n=1 -> 1, n=2 -> 2
    dp = [0] * (n + 1)
    dp[0], dp[1], dp[2] = 1, 1, 2   # base case
    for i in range(3, n + 1):
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD
    return dp[n]

print(num_tilings(3))   # 5
print(num_tilings(4))   # 11
print(num_tilings(30))  # 312342182

5
11
312342182