[leetcode #790] Domino and Tromino Tiling

Problem

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

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 109 + 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 1:

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

Example 2:

Input: n = 1
Output: 1

Constraints:

・ 1 <= n <= 1000

Idea

これはとても面白い問題です.与えられた2種類のドミノ骨牌を用いて2×n板を作製する場合,いくつかの可能な状況を見つければよい.
もちろんdp解でよいと考え,dpをどのように設計するかを考えた.
まず横長を基準に可能な数を考えた.
1.幅が1の場合、Domino Tileを立てる場合があります.dp(1) = 1
2.幅が2の場合、縦または横に2つのDomino Tileがリストされる場合があります.dp(2) = 2
3.幅が3の場合は、ドミノタイルを立てて2番で作った磁器の板を貼り合わせ、2枚のドミノタイルを水平に作り、1番で作った磁器の板を貼り合わせて、2枚のTrimonoタイルをつなぎます.dp(2) = 2 + 1 + 2
n=4から,前に計算したdpを用いない2つの方法が無条件に存在する.したがって、dp式の作成は以下のようになります.
dp[4]=dp[1]x 2(Trimino tileを使用して幅3のボードを作成)+dp[2]+dp[3]+2(前に作成したボードではなく幅4のボードを作成)
dp[5] = (dp[1] + dp[2]) x 2 + dp[3] + dp[4]
上記の式が出たのは,幅が3より大きい場合,前面に作られたタイルを用いない固有の方法が2つあるためである.
上記の式を用いて、O(N)²)出てきました.通過しましたが、他の解答よりも時間がかかったので、道しるべの解答が見えてきました.
leetcodeのアルゴリズムは次のとおりです.

Create two arrays, ff and pp, of size n+1n+1, where f(k)f(k) represents the number of ways to fully cover a board of width kk and p(k)p(k) represents the number of ways to partially cover a board of width kk (as described in the overview).

Initialize ff and pp according to the following base cases:
・ f(1) = 1f(1)=1 because to fully cover a board of width 1, there is only one way, add one vertical domino.
・ f(2) = 2f(2)=2 because to fully cover a board of width 2, there are two ways, either add two horizontal dominos or add two vertical dominos.
・ p(2) = 1p(2)=1 because to partially cover a board of width 2, there is only one way using an L-shaped tromino (leave the upper-right corner uncovered).

Iterate kk from 22 to nn (inclusive) and at each iteration update ff and pp according to the transition functions we derived in the overview:
・ f(k) = f(k-1) + f(k-2) + 2 * p(k-1)f(k)=f(k−1)+f(k−2)+2∗p(k−1)
・ p(k) = p(k-1) + f(k-2)p(k)=p(k−1)+f(k−2)

Return f(n)f(n) which now represents the number of ways to fully cover a board of width nn.

部品板を計算して、公式を創立して、O(N)に解くことができます!原文を読むと分かりやすいので必ず読んでください.

Solution

class Solution {
    public int numTilings(int n) {
        long[] dp = new long[Math.max(n+1,4)];
        dp[1] = 1;
        dp[2] = 1 + 1;

        for (int i=3; i <= n; i++) {
            for (int j=1; j < i; j++) {
                if (j == 1 || j == 2) {
                    dp[i] += dp[i-j];
                } else {
                    dp[i] += 2 * dp[i-j];
                }
            }
            dp[i] += 2;
            dp[i] %= 1_000_000_007;
        }

        return (int) (dp[n] % 1_000_000_007);
    }
}

次はleetcodeソリューションです.

class Solution {
    public int numTilings(int n) {
        int MOD = 1_000_000_007;
        // handle base case scenarios
        if (n <= 2) {  
            return n;
        }
        // f[k]: number of ways to "fully cover a board" of width k
        long[] f = new long[n + 1];  
        // p[k]: number of ways to "partially cover a board" of width k
        long[] p = new long[n + 1];  
        // initialize f and p with results for the base case scenarios
        f[1] = 1L;
        f[2] = 2L;
        p[2] = 1L;
        for (int k = 3; k < n + 1; ++k) {
            f[k] = (f[k - 1] + f[k - 2] + 2 * p[k - 1]) % MOD;
            p[k] = (p[k - 1] + f[k - 2]) % MOD;
        }
        return (int) (f[n]);
    }
}

Reference

https://leetcode.com/problems/domino-and-tromino-tiling/