790. Domino and Tromino Tiling

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 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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(n²)
• Space complexity: O(n²)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const numTilings = function (n) {
  const MODULO = BigInt(10 ** 9 + 7);
  const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(-1));

  const putTiling = (col1, col2) => {
    if (col1 > n || col2 > n) return 0n;
    if (col1 === n && col2 === n) return 1n;
    if (dp[col1][col2] !== -1) return dp[col1][col2];
    let result = 0n;

    if (col1 === col2) {
      result = (result + putTiling(col1 + 2, col2 + 2)) % MODULO;
      result = (result + putTiling(col1 + 1, col2 + 1)) % MODULO;
      result = (result + putTiling(col1 + 2, col2 + 1)) % MODULO;
      result = (result + putTiling(col1 + 1, col2 + 2)) % MODULO;
    }

    if (col1 - col2 === 1) {
      result = (result + putTiling(col1, col2 + 2)) % MODULO;
      result = (result + putTiling(col1 + 1, col2 + 2)) % MODULO;
    }

    if (col2 - col1 === 1) {
      result = (result + putTiling(col1 + 2, col2)) % MODULO;
      result = (result + putTiling(col1 + 2, col2 + 1)) % MODULO;
    }

    dp[col1][col2] = result;

    return result;
  };

  return Number(putTiling(0, 0));
};