LeetCode 790: Domino and Tromino Tiling Solution

Master LeetCode problem 790 (Domino and Tromino Tiling), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

790. Domino and Tromino Tiling

Medium

Dynamic Programming

Problem Explanation

Explanation:

This problem can be solved using dynamic programming. Let's break down the problem into subproblems. We can place tiles in two ways:

Vertical: Using a 2 x 1 tile
Horizontal: Using a tromino shape

We can consider the states of the board as follows:

dp[i][0]: Number of ways to tile a 2 x i board using vertical tiles only
dp[i][1]: Number of ways to tile a 2 x i board using one horizontal tile at the bottom
dp[i][2]: Number of ways to tile a 2 x i board using one horizontal tile at the top
dp[i][3]: Number of ways to tile a 2 x i board using two horizontal tiles

For each column i, we can transition between these states based on the following observations:

For dp[i][0], we can only place a vertical tile, so dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]
For dp[i][1], we can place a horizontal tile at the bottom. This can be done by placing a vertical tile on top of the horizontal tile in the i-1 column or by placing a horizontal tile in the i-1 column. So, dp[i][1] = dp[i-1][0] + dp[i-1][3]
For dp[i][2], we can place a horizontal tile at the top. This can be done by placing a vertical tile below the horizontal tile in the i-1 column or by placing a horizontal tile in the i-1 column. So, dp[i][2] = dp[i-1][0] + dp[i-1][3]
For dp[i][3], we can place two horizontal tiles. This can be done by placing a horizontal tile in the i-1 column. So, dp[i][3] = dp[i-1][1]

The final answer is the sum of all four states at the nth column.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 790 (Domino and Tromino Tiling)?

This page provides optimized solutions for LeetCode problem 790 (Domino and Tromino Tiling) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 790 (Domino and Tromino Tiling)?

The time complexity for LeetCode 790 (Domino and Tromino Tiling) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 790 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 790 in Java, C++, or Python.

Back to LeetCode Solutions