aboutsummaryrefslogtreecommitdiff
path: root/domino_tromino_tiling.py
blob: bd1c25e82861561d6938cfc2b19c44ac128913f9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 790. Domino and Tromino Tiling

"""
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 a '2 x n' board. since the answer may be very large, return it modulo
10^9+7. in a tiling, every square must be tiled 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.
"""


class Solution(object):
    def numTilings(self, n):
        """
        :type n: int
        :rtype: int
        """
        mod = 10**9 + 7
        if n <= 2:
            return n
        f_prev, g_prev, f_prev2, g_prev2 = 2, 2, 1, 1
        for i in range(3, n + 1):
            filled = f_prev + f_prev2 + 2 * g_prev2
            gap = f_prev + g_prev
            f_prev2, f_prev, g_prev2, g_prev = f_prev, filled, g_prev, gap
        return f_prev % mod


if __name__ == "__main__":
    obj = Solution()
    print(obj.numTilings(n=3))
    print(obj.numTilings(n=1))