[Python3] Dynamic Programming Explained | O(mn(3^ m))
Approach\n\nWe have a grid of size ( m * n ) and we want to fill each grid box with some color with 3 choices. A look at constraints gives some insight on numbe
Approach\n\nWe have a grid of size ( m * n ) and we want to fill each grid box with some color with 3 choices. A look at constraints gives some insight on number of rows being limited to 5 which seems to be a good candidate for a ternary mask (base 3).\n\nLets try to explain this with an exmaple.\nAsume m = 3 and n = 3\n\n```\ninitial state: grid\n. . .\n. . .\n. . .\n\ninitial state: previous column fills [-1 , -1 , -1]\n\nLets assume , we fill top to bottom (column 0) in following manner color 0 , then color 1 then color 2\n\n  0 . .\n  1 . .\n  2 . .\n\nnow column 0 is all filled and we want to start filling column 1\n```\nwe are at index (0 , 1)\nwe are now interested in information on left of it , i.e. same row previous cloumn \nand also interested in information on top of it i.e same column previous row\n**Note only these two cells are ever needed to fill the ongoing box**\n\nOne way of doing it could be to store the **previous** column state in a ternary mask\n\n(Instead of using a ternary mask i am using a tuple of size m (max : 5) which will basically store values in range of [0 , 1 , 2] to give me information on what all colors were filled in the row index of previous column. there is a special value -1 which indicates there was no paint on previous column as its out of boundary (true only for first column))\n\n\nI hope till this point you understand that to start working on partiular column, you need fill information on previous column.\nThe most challenging part of this problem is to prepare the fill state ( mask ) for next column in an optimal way\n\nIts more initutive to explain the preparation part with help of an example\n\n```\n\n0 . .\n1 . .\n2 . .\n\nlets say after some fills on cloumn 1 state of column1 is like\n\n0 2 .\n1 0 .\n2 1 .\n\nNow how to get this information [2 , 0 ,1 ] available for column index 2 ? for matter of fact, same question applies on how to get [0 , 1 , 2 ] information available to column index 1\n\nThe idea is to modify the mask we are presented with to begin the iteration. lets see how\n\n* denotes current cell to find a fill\n\n0 * .\n1 . .\n2 . .\n\nyou can fill this cell with color 1 or 2, lets fill 2 and store this information in ongoing mask at index 0\n\n2 f .\n1 . .\n2 . .\n\nNote f denotes the cell is filled but we have modified the existing mask instead of creating a new one for this column\n\nthe next index to fill is (1 , 1)\n\n2 f .\n1 * .\n2 . .\n\nit needs infomration for the left cell and top cell. If the idea has not sparked yet, let me help you. the left value is still not modified (1) and top value can be obtained from the cell above it (2) which we modifed at previous step\n\nfill this with color 0 and modify mask to 0 \n\n2 f .\n0 f .\n2 * .\n\nfor the next index (2 , 1) top and left values are 0 and 2 respectively. lets fill it with 1 \n\n2 f .\n0 f .\n1 f .\n\nin this way you modified the existing mask and prepared it to fill the next column\n```\n\n\nThe rest code is simple DFS based DP that if you are comfortable with it should not be hard to follow. Do let me know in comments if you want explaination in any certain part of the code\n\nThanks for reading\n\n\n\nHere is the code for your perusal\n```\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        \n        init = tuple([-1]*m)\n        mod = 10**9 + 7\n        \n        @lru_cache(None)\n        def solve(i , j , fill):\n            if j == n:\n                return 1\n            \n            state = list(fill)\n            \n            if i == m-1:\n                ans = 0\n                v1 = state[i]\n                v2 = state[i-1] if i else -1\n                \n                for paint in [0 , 1 , 2]:\n                    if paint != v1 and paint != v2:\n                        state[i] = paint\n                        ans += solve(0 , j+1 , tuple(state))\n                        ans %= mod\n                \n                return ans%mod\n            else:\n                ans = 0\n                v1 = state[i]\n                v2 = -1 if not i else state[i-1]\n                \n                for paint in [0 , 1 , 2]:\n                    if paint != v1 and paint != v2:\n                        state[i] = paint\n                        ans += solve(i+1 , j ,tuple(state))\n                        ans %= mod\n                \n                return ans%mod\n                \n        \n        return solve(0 , 0 , init)%mod\n        \n```
[]