Domino And Tromino Tiling - Leetcode Solution

The Domino and Tromino Tiling problem on LeetCode is a dynamic programming problem that requires finding the number of ways to tile a 2xN board with Domino and Tromino tiles, given that N is an even number. The problem statement can be found on the LeetCode website: https://leetcode.com/problems/domino-and-tromino-tiling

Solution:

This problem can be solved using dynamic programming. We need to find a way to relate the solution to a smaller subproblem. Let's define the following:

T[n] represents the number of ways to tile a 2xN board with Domino and Tromino tiles.

For any N, we can place either a vertical domino, a horizontal domino, or a tromino on the first column of the board. Based on this placement, we can determine the recursive relation between T[n] and its subproblems.

Case 1: Vertical domino is placed in the first column

If a vertical domino is placed in the first column, then the second column must also contain a vertical domino. The rest of the board can be tiled in T[n-2] ways. Therefore, the recursive relation in this case is T[n] = T[n-2].

Case 2: Horizontal domino is placed in the first column

If a horizontal domino is placed in the first column, then the second column must also contain a horizontal domino. The rest of the board can be tiled in T[n-2] ways. Therefore, the recursive relation in this case is T[n] = T[n-2].

Case 3: Tromino is placed in the first column

If a tromino is placed in the first column, then the second column can either have a vertical domino or a horizontal domino. This means that the remaining part of the board can be tiled in two different ways (one with a vertical domino in the second column and the other with a horizontal domino in the second column). The number of ways to tile the rest of the board is T[n-1]. Therefore, the recursive relation in this case is T[n] = T[n-1] + T[n-1] = 2*T[n-1].

The base cases for the recursion are:

• T[0] = 1 (there is only one way to tile an empty board)
• T[2] = 2 (there are two possible ways to tile a 2x2 board)

Using the above recursive relation and base cases, we can build a dynamic programming solution to solve this problem. The time complexity of this solution is O(N) and the space complexity is O(1) as we only need to maintain the values of T[n-2], T[n-1], and T[n] at any point in time.

Code:

Here's the Python code for the dynamic programming solution:

def numTilings(N: int) -> int: if N == 0: return 1 if N == 1: return 0 if N == 2: return 2

t0, t1, t2 = 1, 0, 2
for i in range(3, N+1):
    t0, t1, t2 = t1, t2, 2*t2 + t0
return t2

print(numTilings(2)) # Output: 2 print(numTilings(3)) # Output: 5 print(numTilings(4)) # Output: 11

Explanation:

The above code first checks the base cases where N=0, N=1, and N=2. Then, it initializes t0, t1, and t2 to their corresponding base case values. The for loop iterates from 3 to N and updates t0, t1, and t2 based on the recursive relation we defined. Finally, the function returns the value of T[N]. We can verify the output of the function by running it for a few input values.

1