<p>You have two types of tiles: a <code>2 x 1</code> domino shape and a tromino shape. You may rotate these shapes.</p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/15/lc-domino.jpg" style="width: 362px; height: 195px;" />
<p>Given an integer n, return <em>the number of ways to tile an</em> <code>2 x n</code> <em>board</em>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>In a tiling, every square must be covered 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.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/15/lc-domino1.jpg" style="width: 500px; height: 226px;" />
<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> The five different ways are show above.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

class Solution:
    def numTilings(self, n: int) -> int:

        
        memo = {
            1 : 1,
            2 : 2,
            3 : 5
        }

        def _numTilings(n, fill=0):

            if n in memo:
                return memo[n]
            result = 2 * _numTilings(n-1) + _numTilings(n-3)
            memo[n] = result
            return result


            # fill 0: no filled slots
            # fill 1: bottom slot filled (n inclusive)
            # fill 2: top slot filled (n inclusive)
            # if (n,fill) in memo:
            #     return memo[(n,fill)]
            

            # if fill == 0:
            #     if n == 1:
            #         return 1
            #     if n == 2:
            #         return 2

            #     count = 0
            #     count += _numTilings(n - 1, fill=0) # place one vertical tile
            #     count += _numTilings(n - 2, fill=0) # place 2 horizontal tiles
            #     count += _numTilings(n - 1, fill=1) # place L shaped tile
            #     count += _numTilings(n - 1, fill=2) # place upside down L
            #     memo[(n,fill)] = count
            #     return count

            # elif fill == 1:

            #     if n == 1:
            #         return 0
            #     if n == 2:
            #         return 1
                
            #     count = 0
            #     count += _numTilings(n - 1, fill=2) # plae one horizontal tile on the top row
            #     count += _numTilings(n - 2, fill=0) # place one upside down L backwards on the top row
            #     memo[(n,fill)] = count
            #     return count
            
            # elif fill == 2:
            #     if n == 1:
            #         return 0
            #     if n == 2:
            #         return 1
            #     count = 0
            #     count += _numTilings(n-1, fill=1) # place one horizontal tile on the bottom row
            #     count += _numTilings(n-2, fill=0) # place on L tile on the bottom row upside down
            #     memo[(n,fill)] = count
            #     return count
            
            # return 0

                

        return _numTilings(n) % (10 ** 9 + 7)

        
        

        
        

        # Cases:
        # - remove both tiles on the lft
        # - remove both and top tile
        # - remove both and bottom tile



        
18200