dp+ cache
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python []
class Solution(object):
    def colorTheGrid(self, m, n):
        
        # Initialize the cache
        cache = {}

        def dp(seq, lastRow):
            if seq == m * n:
                return 1

            if (seq, lastRow) in cache:
                return cache[(seq, lastRow)]

            i = seq // m
            j = seq % m
            
            lastRowList = list(lastRow)
            ans = 0
            neighborColors = set()
            
            if i > 0:
                neighborColors.add(lastRowList[j])
            
            if j > 0:
                neighborColors.add(lastRowList[j - 1])

            for c in (0, 1, 2):
                if c not in neighborColors:
                    newLastRow = lastRowList[:]
                    newLastRow[j] = c
                    ans += dp(seq + 1, tuple(newLastRow))
            
            ans = ans % mod
            cache[(seq, lastRow)] = ans  # Cache the result
            return ans

        mod = 10**9 + 7
        return dp(0, tuple([0] * m))

```
['Dynamic Programming', 'Python3']