#### 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!**

Painting a Grid With Three Different Colors

Problem Description

Problem Description

Answer Panel