Domino and Tromino Tiling

This is a beautiful problem from LeetCode (Problem #790).

Problem:

You have two types of tiles: a $2 \times 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 \times n$ board. Since the answer may be very large, return it 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 1: Input: $n=3$; Output: 5. There are five different ways as shown below.

Dynamic Programming Solution

We want to find the number of ways to create a $2 \times n$ rectangular grid using the given dominos and trominos. Let $f(n)$ be the number of ways to create a $2 \times n$ rectangular grid.

We observe that we can create a $2 \times n$ rectangle from the following four distinct configurations:

Case 1

We can create a $2 \times n$ rectangle grid from a $2 \times (n-1)$ rectangular grid by adding a domino vertically as shown:

Since the number of ways to create a $2 \times n$ rectangular grid is $f(n)$, the number of ways to create a $2 \times (n-1)$ rectangular grid is $f(n-1)$. Therefore, Case 1 has $f(n-1)$ possible ways.

Case 2

We can also create a $2 \times n$ rectangle grid from a $2 \times (n-2)$ rectangular grid by adding two dominos horizontally as shown:

Since the number of ways to create a $2 \times n$ rectangular grid is $f(n)$, the number of ways to create a $2 \times (n-2)$ rectangular grid is $f(n-2)$. Therefore, Case 2 has $f(n-2)$ possible ways.

Case 3

Since we are also using trominos, in addition to dominos, we could see that one way to build a $2 \times n$ rectangular grid is to add a tromino to an existing grid, which has a $1 \times 1$ hole at the top right as shown in the following diagram. Let us call this grid with a $1 \times 1$ hole at the top right type $P$ structure.

Let $g(n)$ be the number of ways to create a type $P$ structure that has a bottom length of $n$.

We will find a recurrence expression to determine $g(n)$ below.

Therefore the number of ways to create a type $P$ structure with a bottom length of $n-1$ is $g(n-1)$.

Case 4

We could also build a $2 \times n$ rectangular grid by adding a tromino to an existing grid, which has a $1 \times 1$ hole at the bottom right as shown in the following diagram. Let us call this grid with a $1 \times 1$ hole at the bottom right type $Q$ structure.

Let $h(n)$ be the number of ways to create a type $Q$ structure that has a top length of $n$.

We will find a recurrence expression to determine $h(n)$ below.

Therefore the number of ways to create a type $Q$ structure with a top length of $n-1$ is $h(n-1)$.

Adding all four cases together, we find the total number of ways to create a $2 \times n$ rectangular grid from dominos and trominos is,

\[f(n) = f(n-1) + f(n-2) + g(n-1) + h(n-1).\]

Now, let us determine $g(n)$ and $h(n)$.

Recurrent expression for $g(n)$

We note that a type $P$ structure, shown in the right below, can be constructed in the following 2 ways:

(I) It can be constructed by adding a tromino to a $2 \times (n-3)$ rectangular grid as shown below.

Hence there are $f(n-2)$ possible ways to build a type $P$ structure with a bottom length of $n$, using the above construction.

(II) The type $P$ structure can also be constructed by adding a domino to a type $Q$ structure with a top length of $n-2$ as shown below.

In order to create a type $P$ structure with a bottom length of $n$, we need a type $Q$ structure with a top length of $n-1$. There are $h(n-1)$ possible ways to create a type $Q$ structure with a top length of $n-1$.

Combining the results from (I) and (II) above, we obtain the following recurrent equation for $g(n)$:

\[g(n) = f(n-2) + h(n-1).\]

Recurrent expression for $h(n)$

We note that a type $Q$ structure, shown in the right below, can be constructed in the following 2 ways:

(I) It can be constructed by adding a tromino to a $2 \times (n-3)$ rectangular grid as shown below.

Sine a rectangular grid of size $2 \times n$ can be created in $f(n)$ ways, there are $f(n-2)$ ways a type $Q$ structure with a top length of $n$ can be created.

(II) It can also be constructed by adding a domino to a type $P$ structure with a bottom length of $n-2$ as shown below.

Sine the type $P$ structure with a bottom length of $n$ can be created in $g(n)$ ways, there are $g(n-1)$ ways the type $Q$ structure with a top length of $n-1$ can be created.

Combining the results from (I) and (II) above, we obtain the following recurrent equation for $h(n)$:

\[h(n) = f(n-2) + g(n-1).\]

Having determined the recurrent equations for $g(n)$ and $h(n)$, we can now find $f(n)$, the total number of ways to create a rectangular grid of size $2 \times n$, using the following three recurrences:

\[\begin{align*} f(n) &= f(n-1) + f(n-2) + g(n-1) + h(n-1)\\ g(n) &= f(n-2) + h(n-1)\\ h(n) &= f(n-2) + g(n-1) \end{align*}\]

Initial Values

The following initial values are sufficient to build the complete $f, g, h$ sequences, starting from $n=2$:

• $f[0] = 0$ and $f[1] = 1$.
• $g[1] = 0$.
• $h[1] = 0$.

For example, we find

• When $n = 2$, $f[2] = f[1] + f[0] + g[1] + h[1] = 2$.
• When $n = 3$, $f[3] = f[2] + f[1] + g[2] + h[2] = 2 + 1 + f(1) + h(2) + f(1) + g(2) = 5$.

We will use a dictionary to initialize the values for $n=0, 1$ and construct a DP code as follows:

def numTilings(n):
    f = {0: 1, 1: 1}
    g = {1: 0}
    h = {1: 0}
    for i in range(2, n + 1): 
        f[i] = f[i - 1] + f[i - 2] + g[i - 1] + h[i - 1]
        g[i] = f[i - 2] + h[i - 1]
        h[i] = f[i - 2] + g[i - 1]
    return f[n] % (10 ** 9 + 7)

Runtime: We use a for loop to build the entire sequence, each time computing the value of $f[i]$ from the previously computed values of $f, g,$ and $h$. Therefore, the runtime is $O(n)$. The space complexity is also $O(n)$ as we use 3 dictionaries of size at most $n$.

Back to Dynamic Programming Problems

---

anusha-murali.github.io