790.js

/** ------------------------------------------------------------------------------
 * 
 * 790. Domino and Tromino Tiling
 * Topics: DP
 * https://leetcode.com/problems/domino-and-tromino-tiling/description/?envType=daily-question&envId=2025-05-05
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number} n
 * @return {number}
 */
var numTilings = function (n, dp = new Map()) {
  if (n === 0) return 1
  if (n < 3) return n
  if (dp.has(n)) return dp.get(n)
  const r = 2 * numTilings(n - 1, dp) + numTilings(n - 3, dp)
  dp.set(n, r)
  return r % (10 ** 9 + 7)
}

console.log(numTilings(3))