Domino và Tromino Tiling trong C ++

Giả sử chúng ta có hai loại hình, Domino và Tromino. Chúng có thể được xoay như dưới đây -

Trong một lát gạch, mọi ô vuông phải được bao phủ bởi một viên gạch. Ở đây, hai ô xếp khác nhau nếu và chỉ khi có hai ô liền kề theo 4 hướng trên bảng sao cho chính xác một ô xếp có cả hai ô vuông chiếm bởi một ô.

Cho N thì ta phải tìm có bao nhiêu cách xếp được bảng 2xN? Vì vậy, nếu đầu vào là 3, thì đầu ra sẽ là 5. Vì vậy, cách sắp xếp có thể là [XYZ XXZ XYY XXY XYY] và [XYZ YYZ XZZ XYY XXY], ở đây các chữ cái khác nhau được sử dụng cho các ô khác nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Tạo một mảng có tên dp có kích thước N + 5, đặt dp [1]:=1, dp [2]:=2 và dp [3]:=5
cho tôi trong phạm vi 4 đến N
- dp [i]:=2 * dp [i - 1] + dp [i - 3]
trả về dp [N]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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 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];
   }
};
main(){
   Solution ob;
   cout << (ob.numTilings(3));
}

Domino và Tromino Tiling trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra