跳到主要内容

790.多米诺和托米诺平铺

· 阅读需 2 分钟

1、题干​

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

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

 

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

 

提示：

  • 1 <= n <= 1000

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

2、思路​

动态规划，挺难想到

  • 列的状态有4个：无/上/下/满
  • 状态转移也有4个：
    • dp[i][0] = dp[i-1][3]
    • dp[i][1] = dp[i-1][0] + dp[i-1][2]
    • dp[i][2] = dp[i-1][0] + dp[i-1][1]
    • dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]

3、Code​

function numTilings(n: number): number {
    // 无/上/下/满
    let M = 1e9 + 7, dp = [1, 0, 0, 1];

    for (let i = 2; i <= n; i++) {
        const d0 = dp[3];
        const d1 = (dp[0] + dp[2]) % M;
        const d2 = (dp[0] + dp[1]) % M;
        const d3 = (dp[0] + dp[1] + dp[2] + dp[3]) % M;
        dp = [d0, d1, d2, d3];
    }

    return dp[3];
};

4、复杂度​

  • 时间复杂度： O(n)O(n)
  • 空间复杂度： O(1)O(1)

5、执行结果​

image.png