LeetCode Solutions

790. Domino and Tromino Tiling

Time: $O(N)$

Space: $O(N)$

			

class Solution {
 public:
  int numTilings(int N) {
    constexpr int kMod = 1'000'000'007;

    vector<long> dp(1001, 0);
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;

    for (int i = 4; i <= N; ++i)
      dp[i] = (2 * dp[i - 1] + dp[i - 3]) % kMod;

    return dp[N];
  }
};
			

class Solution {
  public int numTilings(int N) {
    final int kMod = 1_000_000_007;

    long[] dp = new long[1001];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;

    for (int i = 4; i <= N; ++i)
      dp[i] = (2 * dp[i - 1] + dp[i - 3]) % kMod;

    return (int) dp[N];
  }
}
			

class Solution:
  def numTilings(self, N: int) -> int:
    kMod = 1_000_000_007
    dp = [0, 1, 2, 5] + [0] * 997

    for i in range(4, N + 1):
      dp[i] = 2 * dp[i - 1] + dp[i - 3]

    return dp[N] % kMod