{x}
blog image

Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 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 1:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

  • 1 <= n <= 1000

Solution Explanation for Domino and Tromino Tiling

This problem asks to find the number of ways to tile a 2 x n board using 2 x 1 dominoes and trominoes (L-shaped tiles). The solution uses dynamic programming to efficiently calculate the number of tilings.

Understanding the State Transition:

The core idea is to represent the state of a tiling using a 4-state system. Let's consider the state of the last column:

  • State 0: The last column is completely filled.
  • State 1: The top cell of the last column is empty, the bottom is filled.
  • State 2: The bottom cell of the last column is empty, the top is filled.
  • State 3: The last column is completely empty.

We can define a DP array f where f[i] represents the number of ways to tile the board up to the current column with state i. The transition from column k to column k+1 can be expressed as follows:

  • f[0](k+1): To get a fully filled column at k+1, you can have any state at k and extend it appropriately. The number of ways to get state 0 at k+1 is the sum of ways to achieve all four states at k (f[0](k) + f[1](k) + f[2](k) + f[3](k)).

  • f[1](k+1): To have the top empty and bottom filled at k+1, we can only come from states where the bottom is filled at k (f[0](k) and f[2](k)).

  • f[2](k+1): Similarly, to have the bottom empty and top filled at k+1, we can come from states where the top is filled at k (f[0](k) and f[1](k)).

  • f[3](k+1): To have an empty column at k+1, we can only come from a completely filled column at k (f[0](k)).

This transition is then iterated from column 1 to n. The final answer is f[0](n), the number of ways to get a fully filled column at the nth column.

Time Complexity Analysis:

The solution iterates through the columns from 1 to n. For each column, a constant amount of work is done to update the four states. Therefore, the time complexity is O(n). This is linear time, which is very efficient for solving this problem.

Space Complexity Analysis:

The solution uses a constant amount of extra space to store the four states (f array). Therefore, the space complexity is O(1), which is constant space. This is highly efficient in terms of memory usage.

Code Explanation (Python):

class Solution:
    def numTilings(self, n: int) -> int:
        f = [1, 0, 0, 0]  # Initialize states for the first column
        mod = 10**9 + 7
        for i in range(1, n + 1):
            g = [0] * 4  # temporary array to store next column's states
            g[0] = (f[0] + f[1] + f[2] + f[3]) % mod  #transition for state 0
            g[1] = (f[2] + f[3]) % mod #transition for state 1
            g[2] = (f[1] + f[3]) % mod #transition for state 2
            g[3] = f[0] #transition for state 3
            f = g  # update the states for next iteration.
        return f[0] #the final answer is state 0 at column n

The code implements the state transitions described above iteratively. The modulo operation (% mod) is used to handle potential integer overflow. The other languages (Java, C++, Go) implement the same logic with minor syntactic differences.