790.md

790 Domino and Tromino Tiling

Description

link

---

Solution

see solution

---

Code

Complexity T : O(N) M : O(N)

class Solution:
    def numTilings(self, N):
        """
        :type N: int
        :rtype: int
        """
        M = 1000000007
        dp = [1, 2, 5]
        if N <= 3:
            return dp[N - 1]
        
        dp += [0] * (N - 3)
        
        for i in range(4, N + 1):
            dp[i - 1] = 2 * dp[i - 2] + dp[i - 4]
            dp[i - 1] %= M
        
        return dp[-1]