Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/790.html

790. Domino and Tromino Tiling

Level

Medium

Description

We have two types of tiles: a 2x1 domino shape, and an “L” tromino shape. These shapes may be rotated.

XX <- domino

XX <- "L" tromino
X

Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)

Example:

Input: 3
Output: 5
Explanation: 
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY

Note:

• N will be in range [1, 1000].

Solution

Use dynamic programming. For N <= 2, the results are straightforward. If N equals 0 or 1, the result is 1 (note that when N equals 0, no tile is needed, which counts for one way). If N equals 2, the result is 2.

For N >= 3, the board can be tiled by adding one vertical domino after N - 1 columns, which counts for one way, or adding two horizontal dominoes after N - 2 columns, which counts for one way, or adding two trominoes and several dominoes after N - k columns where 3 <= k <= N, which count for two ways for each k.

Let f(N) be the number of ways to tile a 2 x N board. It can be seen that f(0) = 1, f(1) = 1, f(2) = 2, and for N >= 3, f(N) = f(N - 1) + f(N - 2) + (f(0) + f(1) + … + f(N - 3)) * 2. Apply the same recurrence formula for f(N - 1), and it can be induced that for N >= 3, f(N) = f(N - 1) * 2 + f(N - 3). Apply this formula to obtain f(N).

• Java
• C++
• Python
• Go

• class Solution {
      public int numTilings(int N) {
          if (N == 0)
              return 1;
          if (N <= 2)
              return N;
          final int MODULO = 1000000007;
          int prev2 = 1, prev1 = 1, cur = 2;
          for (int i = 3; i <= N; i++) {
              int next = (cur * 2 % MODULO + prev2) % MODULO;
              prev2 = prev1;
              prev1 = cur;
              cur = next;
          }
          return cur;
      }
  }
  

• // OJ: https://leetcode.com/problems/domino-and-tromino-tiling/
  // Time: O(N)
  // Space: O(N^2)
  class Solution {
  public:
      int numTilings(int n) {
          long mod = 1e9 + 7;
          vector<vector<long>> dp(n + 2, vector<long>(n + 2));
          dp[1][1] = 1;
          for (int i = 2; i <= n + 1; ++i) {
              dp[i][i] = (dp[i - 1][i - 1] + dp[i - 1][i - 2] * 2 + dp[i - 2][i - 2]) % mod;
              dp[i][i - 1] = (dp[i - 1][i - 2] + dp[i - 2][i - 2]) % mod;
          }
          return dp[n + 1][n + 1];
      }
  };
  

• class Solution:
      def numTilings(self, n: int) -> int:
          @cache
          def dfs(i, j):
              if i > n or j > n:
                  return 0
              if i == n and j == n:
                  return 1
              ans = 0
              if i == j:
                  ans = (
                      dfs(i + 2, j + 2)
                      + dfs(i + 1, j + 1)
                      + dfs(i + 2, j + 1)
                      + dfs(i + 1, j + 2)
                  )
              elif i > j:
                  ans = dfs(i, j + 2) + dfs(i + 1, j + 2)
              else:
                  ans = dfs(i + 2, j) + dfs(i + 2, j + 1)
              return ans % mod
  
          mod = 10**9 + 7
          return dfs(0, 0)
  
  ############
  
  class Solution:
      def numTilings(self, N):
          """
          :type N: int
          :rtype: int
          """
          dp = [[0] * 2 for _ in range(N + 1)]
          dp[0][0] = 1
          dp[1][0] = 1
          for i in range(2, N + 1):
              dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + 2 * dp[i - 1][1]) % (10 ** 9 + 7)
              dp[i][1] = (dp[i - 2][0] + dp[i - 1][1]) % (10 ** 9 + 7)
          return dp[-1][0]
  

• func numTilings(n int) int {
  	f := [4]int{}
  	f[0] = 1
  	const mod int = 1e9 + 7
  	for i := 1; i <= n; i++ {
  		g := [4]int{}
  		g[0] = (f[0] + f[1] + f[2] + f[3]) % mod
  		g[1] = (f[2] + f[3]) % mod
  		g[2] = (f[1] + f[3]) % mod
  		g[3] = f[0]
  		f = g
  	}
  	return f[0]
  }
  

All Problems

All Solutions