python DP top down
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        @functools.lru_cache(None)\n        def generate(i):\n\n            if i == m:\n                return [""]\n            ans = []\n            for s in {"r", "b", "g"}:\n                for j in generate(i+1):\n                    if not j or s != j[0]:\n                        ans.append(s+j)\n            return ans\n            \n        @functools.lru_cache(None)\n        def dp(i, prev):\n            if i == n:\n                return 1\n            ans = 0\n            if not prev:\n                for p in generate(0):\n                    ans += dp(i+1, p)\n            else:\n                for p in generate(0):\n                    for k in range(len(p)):\n                        if p[k] == prev[k]:\n                            break\n                    else:\n                        ans += dp(i+1, p)\n            return ans \n  \n        return dp(0, "") % (10**9 + 7)\n```
['Dynamic Programming', 'Python3']