Python | Easier to Understand
Foward implementation based on\nhttps://leetcode.com/problems/painting-a-grid-with-three-different-colors/discuss/1330889/Python-O(2mnm)-dp-solution-explained\n
Foward implementation based on\nhttps://leetcode.com/problems/painting-a-grid-with-three-different-colors/discuss/1330889/Python-O(2m*n*m)-dp-solution-explained\n\n```\nfrom functools import lru_cache\n#dfs(i,row) means the number of color configuration based on current configuration of upper part(row)\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        MN = m*n\n        M = 10**9+7\n        @lru_cache(None)\n        def dfs(i, row):\n            if i == MN:\n                return 1\n            r, c = divmod(i, m)\n            res, feasible_colors = 0, {0, 1, 2}\n            if r > 0: feasible_colors.discard(row[0])\n            if c > 0: feasible_colors.discard(row[-1])\n            for color in feasible_colors:\n                res += dfs(i+1,row[1:]+(color,))\n            return res%M\n        return dfs(0, tuple([3]*m))\n```
['Depth-First Search', 'Python']