Domino and Tromino Tiling

class Solution {
public:
    int numOfTilings(int n) {
        int MODULO = 1'000'000'007;
        if (n <= 2) {
            return n;
        }
        long currentTile = 5L;
        long previousTile = 2L;
        long tileBeforePrevious = 1L;
        for (int i = 4; i < n + 1; ++i) {
            long temp = previousTile;
            previousTile = currentTile;
            currentTile = (2 * currentTile + tileBeforePrevious) % MODULO;
            tileBeforePrevious = temp;
        }
        return static_cast<int>(currentTile);
    }
};

This C++ program solves the problem of counting the number of ways to tile a 2 x N board using dominoes (1 x 2 tiles) and trominoes (L-shaped tiles). The class Solution includes the function numOfTilings which takes an integer n representing the length of the board.

1. The function starts by defining MODULO to handle large numbers, ensuring that all arithmetic is done under modulo (1,000,000,007) to prevent overflow.
2. It handles base cases directly:
   • If n is less than or equal to 2, the function returns n, as there are exactly n ways to tile a 2xN board when N is either 1 or 2.
3. For n > 2, it initializes the variables currentTile, previousTile, and tileBeforePrevious to 5, 2, and 1 respectively. These variables will track the number of ways to tile smaller sections of the board and use them to build up to the solution for n.
4. The for-loop runs from 4 to n + 1, updating:
   • currentTile as the sum of twice the currentTile and tileBeforePrevious, all under modulo operation.
   • The values of previousTile and tileBeforePrevious get adjusted to shift the sequence forward.
5. At the end of the loop, currentTile holds the number of ways to tile the board of size 2 x n. This value is cast to an int and returned.

The approach efficiently calculates the result using dynamic programming principles to build up the solution iteratively while leveraging modulo arithmetic to manage large intermediate results.

class Solution {
    public int tilingWays(int tiles) {
        final int MODULO = 1_000_000_007;
        if (tiles <= 2) {
            return tiles;
        }
        long current = 5L;
        long prev = 2;
        long prevPrev = 1;
        for (int i = 4; i <= tiles; ++i) {
            long temp = prev;
            prev = current;
            current = (2 * current + prevPrev) % MODULO;
            prevPrev = temp;
        }
        return (int) (current % MODULO);
    }
}

In the given Java program, the problem of "Domino and Tromino Tiling" is addressed with a dynamic programming approach. Here's a breakdown of how the solution method tilingWays calculates the number of ways to tile a board of length tiles using dominos and trominos.

• An integer constant MODULO is defined to ensure that the result is computed within a mod of 1,000,000,007, which prevents overflow issues and keeps numbers manageable.

• Edge cases for small values of tiles are directly returned at the beginning. If tiles is 2 or less, the function returns tiles itself, as 1 and 2 can only be tiled in 1 and 2 ways, respectively.

• Initialize current, prev (previous), and prevPrev (second previous) to represent the number of ways to tile smaller configurations. This setup helps to build the solution iteratively.

• A loop starts from 4 up to tiles. Within each iteration:

  • The current value is calculated based on 2 times the current number of ways plus the number of ways two steps back (prevPrev). This recursion relation reflects the addition of new tiles to previously solved configurations.
  • prevPrev is updated to the old prev.
  • prev is updated to the current value before updating it.

• Finally, the result is adjusted with the modulus operation to ensure it respects the MODULO limitation.

This algorithm efficiently computes the tiling ways using the properties of dynamic programming to reuse past calculations, reducing the time complexity compared to naive methods.

class Solution:
    def countTilings(self, n: int) -> int:
        MODULO = 1_000_000_007
        if n <= 2:
            return n
        current = 5
        last = 2
        lastTwo = 1
        for iteration in range(4, n + 1):
            temp = last
            last = current
            current = (2 * current + lastTwo) % MODULO
            lastTwo = temp
        return current

In the provided Python solution, the function countTilings calculates the number of ways to tile a 2 x n board using dominos and trominos. The function employs dynamic programming, leveraging memoization to efficiently store and calculate results.

Here's a breakdown of how the solution works:

• Initial Conditions:

  • When n is 1 or 2, the result is direct: 1 for n = 1 and 2 for n = 2.
  • The variable MODULO constrains the result within a range, specifically 1,000,000,007, to manage larger numbers and avoid overflow issues.

• Dynamic Programming Transition:

  • Starting from n = 3, the function initializes three variables current, last, and lastTwo, corresponding to the number of ways to tile 2 x (n-1) and 2 x (n-2) boards, respectively.
  • As the loop proceeds from n = 4 onward, current is updated based on the previous two states (last, lastTwo), considering the unique ways dominos and trominos can fit into the board layout.

• Loop Execution:

  • The loop updates the values of current, last, and lastTwo by iterating from 4 to n:
    • lastTwo holds the number of ways to tile the board of size n-2.
    • last temporarily holds the value of current before current is updated, ensuring that the previous state is kept for the next calculation.
  • The result for each iteration, represented as current, is adjusted for modulo 1_000,000,007 to maintain the results within the specified limit.

The functionality of the solution leans on the mathematical relationships between states (current, last, and lastTwo) to build up to the solution for a 2 x n board size, ensuring efficiency and avoiding calculation of redundant states. With these steps, the program provides an effective way to understand dynamic transitions in domino and tromino tiling problems.