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