Problem statement

https://binarysearch.com/problems/Tromino-Theory/

Solution

Equal to Leetcode 0790 Domino and Tromino Tiling

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(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]