0790. Domino and Tromino Tiling¶
题目信息¶
- 题号:
0790
- 难度:
Medium
- 主题:
棋盘覆盖、组合计数、取模
- 原题:
- 重点:
使用可旋转的
2 x 1多米诺和 L 形三格托米诺完整覆盖2 x n棋盘;不能重叠或留空,返回不同铺法数对10^9 + 7取模后的结果
题目重述¶
有两类可任意旋转的拼块:覆盖两个相邻格子的 2 x 1 多米诺,以及覆盖三个格子的 L 形托米诺。给定整数 n,请用这些拼块完整覆盖一个 2 x n 棋盘。
每个格子必须恰好被一个拼块覆盖,拼块不能超出棋盘或相互重叠。若两种覆盖中存在一对四方向相邻格子,在其中一种覆盖里属于同一块拼块、而在另一种覆盖里不属于同一块拼块,则视为不同铺法。
返回不同铺法的数量。由于结果可能很大,需要对 10^9 + 7 取模。1 <= n <= 1000。
自建示例¶
二列棋盘只有两种完整铺法:
输入:n = 2
输出:2
解释:一种铺法使用两块竖直多米诺,分别覆盖左右两列;另一种铺法使用两块水平多米诺,分别覆盖上下两行。单块 L 形托米诺只能覆盖三个格子,无法单独填满四格棋盘,因此不存在第三种铺法。
四列棋盘开始出现更多托米诺组合:
输入:n = 4
输出:11
解释:设 ``f(n)`` 为完整覆盖 ``2 x n`` 棋盘的铺法数。按最右侧完整结构分类可得 ``f(n) = 2 * f(n - 1) + f(n - 3)``;已知 ``f(1) = 1``、``f(2) = 2``、``f(3) = 5``,所以 ``f(4) = 2 * 5 + 1 = 11``。这 11 种铺法包含纯多米诺方案以及成对使用不同朝向托米诺的方案。