Chương trình đếm số lượng cấu hình có để lấp đầy khu vực với dominos và trominos trong C ++

Giả sử chúng ta có hai hình dạng, Domino và Tromino. Dominos có hình dạng 2 x 1 và Trominos có hình dạng giống như chữ ‘L’. Chúng có thể được xoay như dưới đây -

Nếu chúng ta có một số n, chúng ta phải tìm số cấu hình để điền vào một bảng 2 x n với hai loại mảnh này. Như chúng ta đã biết trong việc lát gạch, mọi ô vuông đều phải được lát gạch.

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]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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));
}

Chương trình đếm số lượng cấu hình có để lấp đầy khu vực với dominos và trominos trong C ++

Ví dụ

Đầu vào

Đầu ra