790 Domino and Tromino Tiling 多米諾和托米諾平鋪

Description:
You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

tile

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example:

Example 1:

domino

Input: n = 3
Output: 5
Explanation: The five different ways are show above.

Example 2:

Input: n = 1
Output: 1

Constraints:

1 <= n <= 1000

題目描述:
有兩種形狀的瓷磚：一種是 2x1 的多米諾形，另一種是形如 "L" 的托米諾形。兩種形狀都可以旋轉(zhuǎn)。

XX  <- 多米諾

XX  <- "L" 托米諾
X

給定 N 的值，有多少種方法可以平鋪 2 x N 的面板？返回值 mod 10^9 + 7。

（平鋪指的是每個(gè)正方形都必須有瓷磚覆蓋。兩個(gè)平鋪不同，當(dāng)且僅當(dāng)面板上有四個(gè)方向上的相鄰單元中的兩個(gè)，使得恰好有一個(gè)平鋪有一個(gè)瓷磚占據(jù)兩個(gè)正方形。）

示例 :

輸入: 3
輸出: 5
解釋:
下面列出了五種不同的方法，不同字母代表不同瓷磚：

XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY

提示:

N 的范圍是 [1, 1000]

思路:

動(dòng)態(tài)規(guī)劃
先窮舉出 n <= 4 的所有情況找規(guī)律

    a
    a
n = 1 -> 1
    ab     aa
    ab     bb
n = 2 -> 2
    abc    abb    aac    aab    abb    
    abc    acc    bbc    abb    aab
n = 3 -> 5
    abcd   abcc   abbd   abbc   abcc   aacd   aacc   abbc   aabc   abbc   aacc
    abcd   abdd   accd   abcc   abbc   bbcd   bbdd   aabc   abbc   aacc   abbc
n = 4 -> 11

設(shè) f(n) 表示 n 對(duì)應(yīng)的擺法數(shù)目
可以觀察到 n = 4, 實(shí)際上由 n = 3 及 n = 2, n = 1, 還有兩個(gè)特殊擺法 (f(0)) 組成
令 f(0) = 1
f(4) = f(3) + f(2) + 2 * (f(1) + f(0))
f(5) = f(4) + f(3) + 2 * (f(2) + f(1) + f(0))
f(n) = f(n - 1) + f(n - 2) + 2 * (f(n - 3) + ... + f(0))
f(n - 1) = f(n - 2) + f(n - 3) + 2 * (f(n - 4) + ... + f(0))
f(n) - f(n - 1) = f(n - 1) + f(n - 3)
f(n) = f(n - 3) + 2 * f(n - 1)
可以用動(dòng)態(tài)規(guī)劃, 由于 f(n) 只和前面 3 項(xiàng)相關(guān)可以將空間復(fù)雜度壓縮到 1
時(shí)間復(fù)雜度為 O(n), 空間復(fù)雜度為 O(1)

代碼:
C++:

class Solution 
{
public:
    int numTilings(int n) 
    {
        int a = 1, b = 1, c = 2, m = 1000000007, cur = 0;
        for (int i = 3; i <= n; i++) 
        {
            cur = ((c << 1) % m + a % m) % m;
            a = b;
            b = c;
            c = cur;
        }
        return n > 1 ? c : a;
    }
};

Java:

class Solution {
    public int numTilings(int n) {
        int a = 1, b = 1, c = 2, m = 1000000007, cur = 0;
        for (int i = 3; i <= n; i++) {
            cur = ((c << 1) % m + a % m) % m;
            a = b;
            b = c;
            c = cur;
        }
        return n > 1 ? c : a;
    }
}

Python:

class Solution:
    def numTilings(self, n: int) -> int:
        a, b, c = 1, 1, 2
        for i in range(3, n + 1):
            a, b, c = b, c, (c << 1) + a
        return c % 1000000007 if n > 1 else a