806. Domino And Tromino Tiling¶

LeetCode Problem View on GitHub

806. Domino and Tromino Tiling

Medium

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¶

class Solution {
    static int mod = (int)(1e9 + 7);
    public int numTilings(int n) {
        long dp[] = new long[n + 3];
        dp[0] = 1; dp[1] = 2; dp[2] = 5;
        for (int i = 3; i < n; i++) dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % mod;
        return (int)dp[n - 1];
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here