diff options
Diffstat (limited to 'domino_tromino_tiling.py')
-rw-r--r-- | domino_tromino_tiling.py | 34 |
1 files changed, 34 insertions, 0 deletions
diff --git a/domino_tromino_tiling.py b/domino_tromino_tiling.py new file mode 100644 index 0000000..bd1c25e --- /dev/null +++ b/domino_tromino_tiling.py @@ -0,0 +1,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)) |