Leetcode 0790 Domino and Tromino Tiling

Problem statement

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

Solution

As any problem with tiling, here we need to write down recurrent equations. Let $F_n$ be number of tilings for $(n+1)\times 2$ board and $G_n$ be number of tilings for $(n+1) \times 2$ board with one cell added. Then it can be shown that $F_n = F_{n-1} + F_{n-2} + 2\cdot G_{n-2}$ and $G_n = G_{n-1} + F_{n-1}$ and $F_0 = 1, F_1 = 2, G_0 = 1, G_1 = 2$.

Complexity

Time and space complexity will be O(n).

Code

class Solution:
    def numTilings(self, N):
        M = 10**9 + 7
        if N <= 2: return N
        F = [1, 2] + [0]*(N-2)
        G = [1, 2] + [0]*(N-2)
        for i in range(2, N):
            F[i] = (F[i-1] + F[i-2] + 2*G[i-2]) % M
            G[i] = (G[i-1] + F[i-1]) % M
            
        return F[-1]

Remark

Moreover it can be shown, that $F_n = 2\cdot F_{n-1}+F_{n-3}$, so it can be written using only O(1) memory. Also, as for any recurrent equation, it can be solved in O(log n) * Q^3, if we evaluate power of the transition matrix A = [[2, 0, 1], [1, 0, 0], [0, 1, 0]], where Q = 3 is size of this matrix. We need to evaluate b * A^n, where b = [0, 1, 1] are starting positions.