Domino and Tromino Tiling LeetCode solution in Python

1
# Runtime: 35 ms (Top 93.5%) | Memory: 16.27 MB (Top 85.2%)
2

3

4
class Solution(object):
5
    def numTilings(self, n):
6
        dp = [1, 2, 5] + [0] * n
7
        for i in range(3, n):
8
            dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % 1000000007
9
        return dp[n - 1]