สมมติว่าเรามีสองรูปร่าง Domino และ Tromino โดมิโนมีรูปร่าง 2 x 1 และทรอมิโนมีรูปร่างคล้าย 'L' สามารถหมุนได้ดังนี้ -
ถ้าเรามีตัวเลข n เราต้องหาจำนวนการกำหนดค่าเพื่อเติมบอร์ด 2 xn ด้วยชิ้นส่วนสองประเภทนี้ อย่างที่ทราบกันดีว่าการปูกระเบื้อง ทุกตารางต้องมีกระเบื้อง
ดังนั้นหากอินพุตเป็น 3 เอาต์พุตจะเป็น 5 ดังนั้นการจัดเรียงอาจเป็น [XYZ XXZ XYY XXY XYY] และ [XYZ YYZ XZZ XYY XXY] ในที่นี้จะมีการใช้ตัวอักษรต่างกันสำหรับไทล์ต่างๆ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างอาร์เรย์ชื่อ dp ขนาด N + 5 ตั้งค่า dp[1] :=1 dp[2] :=2 และ dp[3] :=5
-
สำหรับฉันอยู่ในช่วง 4 ถึง N
-
dp[i] :=2*dp[i − 1] + dp[i − 3]
-
-
กลับ dp[N]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
3
ผลลัพธ์
5
