[Python] O(2^m*n*m) dp solution, explained
Solution 1\nThe idea is to go row by row and check that we do not have conflicts of colors in each row and between rows.\n\n1. C is all candidates for row, that
#### Solution 1\nThe idea is to go row by row and check that we do not have conflicts of colors in each row and between rows.\n\n1. `C` is all candidates for row, that is all rows, such that we do not have conflicts among horizontal adjacent cells.\n2. Also create dictionarly `d`: where for each candidate we collect all possible options for the next line such that we do not have vertical conflicts.\n3. Finally, we go level by level and for each `c1` among candidates and then for each `c2 in d[c1]`, we update number of options for `dp2[c2]`. In the end of iteration we update `dp = dp2`.\n\n#### Complexity\nWe have `O(3^m * m)` complexity to generate `C`. In fact we will have `3*2^(m-1)` options for each row. Then when we check all pairs we do `O(9^2^(2m-2)  * m) = O(4^m * m)` ways. Then we have `O(4^m * m)` complexity for each level, so total time complexity is `O(4^m * n * m)`. Space complexity is `O(4^m)`.\n\n#### Code\n```python\nclass Solution:\n    def colorTheGrid(self, m, n):\n        C = [c for c in product([0,1,2], repeat = m) if all(x!=y for x,y in zip(c, c[1:]))]\n\n        MOD, dp, d = 10**9 + 7, Counter(C), defaultdict(list)\n\n        for c1, c2 in product(C, C):\n            if all(x != y for x, y in zip(c1, c2)):\n                d[c1].append(c2)\n\n        for _ in range(n-1):\n            dp2 = Counter()\n            for c1 in C:\n                for c2 in d[c1]:\n                    dp2[c2] = (dp2[c2] + dp[c1]) % MOD\n            dp = dp2\n\n        return sum(dp.values()) % MOD\n```\n\n#### Solution 2\n\nActually, there is solution with better complexity! The idea is Problem **1659. Maximize Grid Happiness** , you can find more explanations here: https://leetcode.com/problems/maximize-grid-happiness/discuss/936467/Python-Short-and-clean-dp-with-diagram-expained\n\n![image](https://assets.leetcode.com/users/images/95ef3564-fcd2-4f0e-901c-03cc140172d0_1626014693.972445.png)\n\nWe use so-called dp with broken profile, and on each step we try to add one more element, checking two neigbours. \n\n#### Complexity: \nWe have `mn` states for `index` and `O(2^m)` states for `row`. So, we have in total `O(2^m * m * n)` states, which of them have length `O(m)`. So, total space and time complexity here is `O(2^m * m^2*n)`\n\n#### Code 1\n```python\nclass Solution:\n    def colorTheGrid(self, m, n):\n        \n        @lru_cache(None)\n        def dp(index, row):\n            if index == -1: return 1\n            \n            R, C = divmod(index, m)\n            \n            ans, allowed = 0, {0, 1, 2}\n            \n            if C < m - 1: allowed.discard(row[0])\n            if R < n - 1: allowed.discard(row[-1])\n            \n            for val in allowed:\n                ans += dp(index-1, (val,) + row[:-1])\n                \n            return ans % MOD\n        \n        MOD = 10**9 + 7\n        return dp(m*n-1, tuple([3]*m)) % MOD\n```\n\nComplexity can be reduced to just `O(2^m * n * m)` if we use bitmasks instead of tuples: `00`, `01`, `10`, `11` represents `0, 1, 2, 3`, and we spend two bits for each of `m` element of row, so we keep number with `2m` bits. Because of `lru_cache` we use here we have quite big armotization constant, so to make it really fast you can use classical table dp.\n\n**Update** Actually, number of states is approximately `O(2^m * n * m * 2.25)`, because our row consist of two parts, each of which can start from any color and then we can take always no more than `2` options.\n\n#### Code 2\n```python\nclass Solution:\n    def colorTheGrid(self, m, n):\n        @lru_cache(None)\n        def dp(index, row):\n            if index == -1: return 1\n            \n            R, C = divmod(index, m)\n            \n            ans, allowed = 0, {0, 1, 2}\n            \n            if C < m - 1: allowed.discard(row >> (2*m-2))\n            if R < n - 1: allowed.discard(row & 3)\n            \n            for val in allowed:\n                ans += dp(index-1, (row >> 2) + (val<<(2*m-2)))\n                \n            return ans % MOD\n        \n        MOD = 10**9 + 7\n        return dp(m*n-1, (1<<(2*m)) - 1) % MOD\n```\n\nActually we can implement the same logic without recursion, and I thought that it will make code several times faster, but no it is not. I need to inverstigate why, does anybody have any ideas? One theory is that `m` is quite small here, and because of hidden constants are quite big, we can not bead the first method.\n\n#### Code 3\n```python\nclass Solution:\n    def colorTheGrid(self, m, n):\n        dp, MOD = {(1<<(2*m)) - 1: 1}, 10**9 + 7\n        \n        for index in range(m*n-1, -1, -1):\n            dp2 = Counter()\n            R, C = divmod(index, m)\n            \n            for row in dp:\n                allowed = {0, 1, 2}\n                if C < m - 1: allowed.discard(row >> (2*m-2))\n                if R < n - 1: allowed.discard(row & 3)\n\n                for val in allowed:\n                    row2 = (row >> 2) + (val<<(2*m-2))\n                    dp2[row2] = (dp2[row2] + dp[row]) % MOD \n            \n            dp = dp2\n    \n        return sum(dp.values()) % MOD\n```\n\n**Update** as it happen, indeed when we increase `m` with fixed `n = 1000` and we an fell difference starging from `m = 10`.\n\n| m  | Solution 1 time | Solution 2 time |\n|----|-----------------|-----------------|\n| 1  | 0.007           | 0.016           |\n| 2  | 0.015           | 0.041           |\n| 3  | 0.032           | 0.130           |\n| 4  | 0.094           | 0.327           |\n| 5  | 0.290           | 0.847           |\n| 6  | 0.859           | 2.006           |\n| 7  | 2.612           | 4.638           |\n| 8  | 7.965           | 10.73           |\n| 9  | 24.51           | 24.21           |\n| 10 | 75.61           | 56.07           |\n| 11 |     235.0           |     125.2           |\n| 12 |      730.2          |      279.6           |\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Dynamic Programming']