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

numTilings.js

/**
 * Calculates the number of ways to tile a 2 × n board using dominos and trominos.
 * @param {number} n - The width of the board.
 * @return {number} - The number of valid tilings, modulo 10^9 + 7.
 */
var numTilings = function (n) {
    const MOD = 1e9 + 7; // Modulo constraint to prevent overflow

    // Base cases for small values of n
    if (n === 1) return 1; // Only one vertical domino fits
    if (n === 2) return 2; // Two configurations: vertical or horizontal dominos

    // Create an array to store computed values
    const dp = new Array(n + 1).fill(0);
    
    // Initialize base cases
    dp[0] = 1;  // 1 way to fill an empty board (trivial case)
    dp[1] = 1;  // 1 way for n = 1 (single vertical domino)
    dp[2] = 2;  // 2 ways for n = 2 (two vertical dominos OR two horizontal dominos)

    // Fill the dp array using the recurrence relation
    for (let i = 3; i <= n; i++) {
        /*
         * Recurrence relation:
         * - 2 * dp[i - 1]: Extending a (2 × (i-1)) board with either a vertical domino or tromino.
         * - dp[i - 3]: Accounts for special cases where a tromino creates unique configurations.
         */
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MOD; // Apply modulo at each step to keep values manageable
    }

    return dp[n]; // Return the computed value for n
};