Domino and Tromino Tiling

Problem Description

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 10^9 + 7.

Key Insights

• The problem can be solved using dynamic programming.
• The number of ways to tile a 2 x n board can be derived from the previous states.
• A 2 x 1 domino covers two cells vertically or horizontally, while a tromino covers three cells.
• The recurrence relation can be established based on the configurations of the tiles.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

We can use dynamic programming to solve this problem. We define an array dp where dp[i] represents the number of ways to tile a 2 x i board. The recurrence can be established as follows:

• dp[i] = dp[i-1] + dp[i-2] * 2 for i >= 2, where dp[1] = 1 and dp[2] = 2.
• The first term dp[i-1] accounts for placing a domino vertically, while the second term dp[i-2] * 2 accounts for placing two horizontal dominoes or one tromino.

We will also take the result modulo 10^9 + 7 to handle large numbers.

Code Solutions