C++でのDominoとTrominoのタイリング

タイリングでは、すべての正方形をタイルで覆う必要があります。ここで、2つのタイルは、ボード上に2つの4方向に隣接するセルがあり、タイルの1つだけが両方の正方形をタイルで占めている場合にのみ異なります。

Nが与えられた場合、2xNボードをタイリングできる方法をいくつ見つける必要がありますか？したがって、入力が3の場合、出力は5になります。したがって、配置は[XYZ XXZ XYYXXYXYY]と[XYZYYZXZZ XYY XXY]になります。ここでは、タイルごとに異なる文字が使用されます。

これを解決するには、次の手順に従います-

• サイズN+5のdpという配列を作成し、dp [1]：=1、dp [2]：=2およびdp[3]：=5

  を設定します。

• 4からNの範囲のiの場合

  • dp [i]：=2 * dp [i – 1] + dp [i – 3]

• dp [N]

  を返します

例（C ++）

理解を深めるために、次の実装を見てみましょう-

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

入力

3

出力

5