Domino and Tromino Tiling

Leetcode Problem:

• Domino and Tromino Tiling

Summary

• The problem requires finding the number of ways to tile a 2 x n board with 2 x 1 dominoes and a tromino shape, with the answer being modulo 10^9 + 7.

Approach

• The solution uses dynamic programming to calculate the number of ways to tile the board
• It initializes an array `memo` to store the number of ways to tile a board of length `i`, and then iterates from `i = 4` to `n` to calculate the number of ways to tile a board of length `i`
• For each `i`, it calculates the number of ways to tile a board of length `i` by considering the number of ways to tile a board of length `i-1` and `i-2`, and adds the number of ways to tile a board of length `i-3` to the result, taking into account the modulo operation to avoid overflow.

Complexity

• O(n)

Explanation

• The solution uses a dynamic programming approach to calculate the number of ways to tile the board
• It initializes an array `memo` to store the number of ways to tile a board of length `i`, and then iterates from `i = 4` to `n` to calculate the number of ways to tile a board of length `i`
• For each `i`, it calculates the number of ways to tile a board of length `i` by considering the number of ways to tile a board of length `i-1` and `i-2`, and adds the number of ways to tile a board of length `i-3` to the result, taking into account the modulo operation to avoid overflow
• The time complexity of the solution is O(n) because it iterates from `i = 4` to `n` once, and the space complexity is O(n) because it stores the number of ways to tile a board of length `i` in the `memo` array.

Solution Code:

#define MOD 1000000007
class Solution {
public:
    int memo[1001];
    int numTilings(int n) {
        memo[0] = 1;
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 5;
        for(int i = 4; i <= n; i++){
            memo[i] = (memo[i-1] + memo[i-2])%MOD;
            for(int j = i - 3; j >= 0; j--){
                memo[i] += (memo[j]*2)%MOD;
                memo[i] %= MOD;
            }
        }
        return memo[n];
    }
};