本文共 936 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算用两种形状的瓷砖（多米诺和托米诺）铺满2xN的面板的方法数。我们可以使用动态规划来解决这个问题，并通过递推关系来优化计算。

方法思路

我们定义两个函数：

• fe[n] 表示2x2n的面板铺满的方法数。
• fo[n] 表示2x(2n+1)的面板铺满的方法数。

通过递推关系，我们可以得到以下公式：

• fe[n] = fe[n-1] + fe[n-2] + 2*fe[n-3] + 2*fo[n-3]
• fo[n] = fo[n-1] + fe[n-1]

初始条件如下：

• fe[1] = 1
• fe[2] = 2
• fo[1] = 2
• fo[2] = 2

解决代码

class Solution {    public int numTilings(int N) {        long a = new long[N + 3];        long b = new long[N + 3];        int mod = 10_000_000_7;        a[1] = 1;        a[2] = 2;        b[2] = 1;        if (N >= 3) {            for (int i = 3; i <= N; i++) {                a[i] = (a[i-1] + a[i-2] + 2 * b[i-1]) % mod;                b[i] = (b[i-1] + a[i-2]) % mod;            }        }        return (int) a[N];    }}

代码解释

这种方法的时间复杂度为O(N)，空间复杂度为O(1)，因为我们只使用了固定数量的存储空间。

转载地址：http://kpki.baihongyu.com/