Medium

题目描述

你有两种类型的瓷砖：一种是 2 x 1 的多米诺形状，另一种是三联骨牌形状。你可以旋转这些形状。

给定一个整数 n，返回铺满 2 x n 的棋盘的方案数。由于答案可能很大，请返回对 10^9 + 7 取模的结果。

在铺设中，每个正方形都必须被瓷砖覆盖。当且仅当棋盘上有两个 4 方向相邻的单元格，其中恰好有一种铺设方法使两个正方形都被一块瓷砖占据时，两种铺设才不同。

示例 1：

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

示例 2：

输入：n = 1
输出：1

提示：

  • 1 <= n <= 1000

解题思路

这是一道经典的动态规划问题。我们需要分析在 2×n 的棋盘上放置多米诺骨牌（2×1）和三联骨牌（L形）的方案数。

状态设计思路： 我们可以按列从左到右考虑，对于每一列，可能出现以下几种状态：

  • 状态0：当前列完全填满
  • 状态1：当前列上方有空格，下方填满
  • 状态2：当前列下方有空格，上方填满

状态转移分析：

  • dp[i][0]：前i列完全填满的方案数
  • dp[i][1]：前i列中第i列上方缺失、下方填满的方案数
  • dp[i][2]：前i列中第i列下方缺失、上方填满的方案数

转移方程：

  • dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-2][0]
  • dp[i][1] = dp[i-1][0] + dp[i-1][2]
  • dp[i][2] = dp[i-1][0] + dp[i-1][1]

优化思路： 观察发现 dp[i][1] = dp[i][2]，我们可以简化为两个状态：

  • f[i]：完全填满前i列的方案数
  • p[i]：部分填满第i列的方案数

最终递推关系：f[i] = f[i-1] + f[i-2] + 2*p[i-1]，p[i] = p[i-1] + f[i-2]

这种方法时间复杂度O(n)，空间复杂度O(1)，是推荐解法。

代码实现

class Solution {
public:
    int numTilings(int n) {
        const int MOD = 1000000007;
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        long long f0 = 1, f1 = 2, p1 = 1;
        
        for (int i = 3; i <= n; i++) {
            long long f2 = (f1 + f0 + 2 * p1) % MOD;
            long long p2 = (p1 + f0) % MOD;
            f0 = f1;
            f1 = f2;
            p1 = p2;
        }
        
        return f1;
    }
};

class Solution:
    def numTilings(self, n: int) -> int:
        MOD = 1000000007
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        f0, f1, p1 = 1, 2, 1
        
        for i in range(3, n + 1):
            f2 = (f1 + f0 + 2 * p1) % MOD
            p2 = (p1 + f0) % MOD
            f0, f1, p1 = f1, f2, p2
        
        return f1

public class Solution {
    public int NumTilings(int n) {
        const int MOD = 1000000007;
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        long f0 = 1, f1 = 2, p1 = 1;
        
        for (int i = 3; i <= n; i++) {
            long f2 = (f1 + f0 + 2 * p1) % MOD;
            long p2 = (p1 + f0) % MOD;
            f0 = f1;
            f1 = f2;
            p1 = p2;
        }
        
        return (int)f1;
    }
}

var numTilings = function(n) {
    const MOD = 1000000007;
    
    if (n === 1) return 1;
    if (n === 2) return 2;
    
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    
    for (let i = 3; i <= n; i++) {
        dp[i] = (2 * dp[i-1] + dp[i-3]) % MOD;
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历从3到n的所有位置
空间复杂度O(1) - 只使用常数个变量存储状态