aboutsummaryrefslogtreecommitdiff
path: root/domino_tromino_tiling.cpp
blob: 80a97d0f5199c494209593e2f8e0eac47fbb24e3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include "leetcode.h"
#include <vector>

class Solution {
public:
  int numTilings(int n) {
    int mod = 1e9;
    mod += 7;
    vector<long long> ans(1001, 0);
    ans[1] = 1;
    ans[2] = 2;
    ans[3] = 5;
    if (n <= 3)
      return ans[n];
    for (int i = 4; i <= n; ++i) {
      ans[i] = 2 * ans[i - 1] + ans[i - 3];
      ans[i] %= mod;
    }
    return ans[n];
  }
};

int main() {
  Solution obj;
  cout << obj.numTilings(3); // 5
  cout << endl;
  cout << obj.numTilings(1); // 1
}