Giả sử ta có hai hình dạng: Domino (2x1) và Tromino (hình L). Chúng có thể xoay như hình minh họa.
Cho số n, ta phải tìm số cấu hình để lấp đầy bàn cờ 2 x n bằng hai loại mảnh này. Mọi ô đều phải được phủ bởi mảnh.
Ví dụ n=3, đầu ra=5. Các cách sắp xếp: [XYZ XXZ XYY XXY XYY] và [XYZ YYZ XZZ XYY XXY], chữ cái khác nhau đại diện cho mảnh khác nhau.
Để giải quyết, ta làm theo các bước:
- Tạo mảng dp kích thước N+5, đặt dp[1]=1, dp[2]=2, dp[3]=5.
- for i từ 4 đến N: dp[i] := 2*dp[i-1] + dp[i-3].
- Trả về dp[N].
Xem triển khai dưới đây:
Ví dụ
#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 <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]; } }; main(){ Solution ob; cout << (ob.solve(3)); }
Đầu vào
3
Đầu ra
5