2022-12-24.md

题目

790. Domino and Tromino Tiling

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 10^9 + 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.

思路

只考虑domino

dp[n] = dp[n-1] + dp[n-2]

tromino有4种最小排列：

• 上上（2x4
• 下下（2x4
• 上下（2x3
• 下上（2x3

除了最小排列以外，tromino中间可以插入任意偶数个domino

dp[n] = dp[n-1] + dp[n-2] + 2 * dp[n-3] + 2 * dp[n-4] + ... + 2 * dp[2] + 2 * dp[1]

dp[n+1] = dp[n] + dp[n-1] + 2 * dp[n-2] + ... + 2 * dp[1]
= dp[n] + dp[n-1] + 2 * dp[n-2] + dp[n] - dp[n-1] - dp[n-2]
= 2 * dp[n] + dp[n-2]

代码

var numTilings = function(n) {
  const m = 1e9 + 7
  const dp = [, 1, 2, 5]
  for (let i = 4; i <= n; i++) {
    dp[i] = (2 * dp[i-1] + dp[i-3]) % m
  }
  return dp[n]
}