Domino and Tromino Tiling

#Intuitive Aprroach: O(n2) time and O(n) space
#--------------------Logic--------------------
"""
For every value of n, there are certain ATOMIC (indivisible) tiling patterns that cannot be build from tilings of smaller boards(smaller values of n), thus cannot be obtained recursvely. For example:
(USE DESKTOP MODE)
For n=1                 For n=2               For n=3                 For n=4                     For n=5
x                       x x                   x y y      x x y        x y y z      x x y y        x y y z z      x x y y z
x                       y y                   x x y      x y y        x x z z      x z z y        x x a a z      x a a z z
Vertical                2 Horizontal          Two Trominoes and n-3 Dominoes combo (for n>2) .............................
Domino                  Dominoes
(For these arrangements except for the first and last column no other column has same characters [grids in same column belong to different tiles]; thus pattern is indivisible)
Thus for all n > 2 there exists two such atomic arrangements (this accounts for 2 in the dp equation, explained below)

Thus in order to build the i-tiling we can add these atomic patterns of sizes 1 to i to the right of all possible tilings,dp[j] ; j in [i-1, 0].
let dp[i] = no. of ways to tile 2*i board completely
So: dp[i] =
dp[i-1]*no. of atomic pattern of size 1 (=1) +
dp[i-2]*no. of atomic pattern of size 2 (=1) +
dp[i-3]*no. of atomic pattern of size 3 (=2) +
dp[i-4]*no. of atomic pattern of size 4 (=2) + .... +
dp[0]*no. of atomic patterns of size i                 {dp[0] = 1 (one way: no tiling)}
We consider adding atomic patterns, inorder to avoid problem of overcounting

Thus: dp equation is dp[i] = dp[i-1] + dp[i-2] + 2*(dp[i-3]+dp[i-4]+...+dp[1]+dp[0]) for all n
"""
class Solution(object):
    def numTilings(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1, 1] + [2]*(n-2) #Prepopulating with atomic patterns of sizes 1 to n (1, 1, 2, 2, 2,.....2)
        for i in range(n):
            for j in range(1, i+1):
                dp[i] += dp[i-j] + dp[i-j]*(j>2)
        return dp[-1] % int(1e9+7)

#Refined approach O(n) time and constant auxillary space
"""
Using prefix(/partial) sum like logic
dp[i] = dp[i-1] + dp[i-2] + 2*(dp[i-3]+ ... +dp[0])
      = dp[i-1] + dp[i-3]  + (dp[i-2] + dp[i-3] + 2*(dp[i-4] +...+ dp[0])    ...distributing the 2*dp[i-3] term
      = dp[i-1] + dp[i-3] + dp[i-1]
      = 2*dp[i-1] + dp[i-3]
"""
'''
class Solution(object):
    def numTilings(self, n):
        """
        :type n: int
        :rtype: int
        """
#a is dp[i]; b is dp[i-1]; c is dp[i-2]:  they become dp[i-1], dp[i-2], dp[i-3] in next iteration and so on...
        a, b, c = 1, 1, 0
        for i in range(n-1):
            a, b, c = (2*a + c)%int(1e9+7), a, b
        return a
'''