跳转至

LeetCode: 790. 多米诺和托米诺平铺

1、题目描述

有两种形状的瓷砖:一种是 2x1 的多米诺形,另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

XX  <- 多米诺

XX  <- "L" 托米诺
X

给定 N 的值,有多少种方法可以平铺 2 x N 的面板?返回值 mod 10^9 + 7

(平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同,当且仅当面板上有四个方向上的相邻单元中的两个,使得恰好有一个平铺有一个瓷砖占据两个正方形。)

示例:

输入: 3
输出: 5
解释: 
下面列出了五种不同的方法,不同字母代表不同瓷砖:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY

提示:

  • N 的范围是 [1, 1000]

2、解题思路

  • 动态规划
  • 设置三个数组,分别保存
    • 当前位置无空位
    • 上面留有一个空位
    • 下面留有一个空位
                 |                               
                 |                               
                 |                               
                 |                               
                 v                               

+----------+----------+-------------------------+
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
|          |          |                         |
+----------+----------+-------------------------+
                |                                
                |                                
                v                                
+----------+------------------------------------+
|          |                                    |
|          |                                    |
|          |                                    |
|          |                                    |
|          |                                    |
|          |                                    |
|          +----------+                         |
|                     |                         |
|                     |                         |
|                     |                         |
|                     |                         |
|                     |                         |
|                     |                         |
+---------------------+-------------------------+
+----------+-----------------------+------------+
|          |                       |            |
|          |                       |            |
|          |                       |            |
|          |                       |            |
|          |                       |            |
|          |                       |            |
|          +----------+------------+            |
|                     |                         |
|                     |                         |
|                     |                         |
|                     |                         |
|                     |     ^                   |
|                     |     |                   |
+---------------------+-----+-------------------+
                            |                    
                            |                    
                            |                    
                            |                    
                            |                    

每次更新三种状态即可

for i in range(3, N + 1):
    dp_up[i] = (dp[i - 2] + dp_bottom[i - 1]) % mod_num
    dp_bottom[i] = (dp[i - 2] + dp_up[i - 1]) % mod_num
    dp[i] = (dp[i - 1] + dp[i - 2] + dp_up[i - 1] + dp_bottom[i - 1]) % mod_num
  • 如果想要上角缺失一个,就需要是前面两个空位置放置一个L,或者是前面的下角缺失补上一个水平的
  • 如果想要下角缺失一个,就需要是前面两个空位置放置一个翻转L,或者是前面的上角缺失补上一个水平的
  • 当前位置想要补齐,当前位置补上一个竖直的2*1,加上前面2个都是水平的2*1,加上补上缺失脚的两种情况即可

实例代码:

class Solution:
    def numTilings(self, N: int) -> int:
        if N == 1:
            return 1
        mod_num = 1000000007
        dp = [0] * (N + 1)
        dp_up = [0] * (N + 1)
        dp_bottom = [0] * (N + 1)

        # 初始化

        dp[1] = 1
        dp[2] = 2
        dp_up[2] = 1
        dp_bottom[2] = 1

        for i in range(3, N + 1):
            dp_up[i] = (dp[i - 2] + dp_bottom[i - 1]) % mod_num
            dp_bottom[i] = (dp[i - 2] + dp_up[i - 1]) % mod_num
            dp[i] = (dp[i - 1] + dp[i - 2] + dp_up[i - 1] + dp_bottom[i - 1]) % mod_num

        return dp[-1]