Thought Process, 3^(mn)mn -> n((2^(m-2))^2), 95% ever
foreword: I\'m trying to share logical thought process for deriving various solutions from scratch with minimum tricks, if you think this style helps, please ki
*foreword: I\'m trying to share logical thought process for deriving various solutions from scratch with minimum tricks, if you think this style helps, please kindly **upvote** and/or **comment** for encouragement, or leave your thoughts to tune the content, thanks and happy thought processing :)*\n\n1) naive: find all [color choices] of [all cells] and check if meet constraint  -> each cell has 3 color choices, there are m*n cells, so total ways are: `3*3*...*3` with `m*n` terms \n\t- -> Time: `O(3^(m*n) * (m*n))`\n\n2) is there any processed info can be reused? \n  -> row=i ways only depends on row=i-1 ways if all ways before are embedded into row=i-1 \n```\nrow  colors\ni-3  ***     ***\ni-2  ***     ***\ni-1  GRG     GBR\ni    RGB     RGB\n```\n\n3) each row way as a state, each row=i state has possible transitions from all row=i-1\'s states, and filtered by constraint (color of adjacent cell differs), so state transition per row is:\n  n_ways(row=i, state=way1) = valid(n_ways(row=i-1, state=way1)) + valid(n_ways(row=i-1, state=way2)) + ...\n  n_ways(row=i, state=way2) = valid(n_ways(row=i-1, state=way1)) + valid(n_ways(row=i-1, state=way2)) + ...\n  ...\n  the number of state transitions are: `[number of row=i\'s states] * [number of row=i-1\'s states]`\n  \n4) base on 3). each row has 3^m or 3^n states, since m is much smaller, so we choose m as column and states per row will be 3^m . so \n\t- [number of state transitions] = [number of row=i\'s states] * [number of row=i-1\'s states] = (3^m) * (3^m) = (3^m)^2\n\t- -> Total Time: [number of rows] * [state transitions] = `n * ( (3^m)^2 )`\n\t- -> `n * 243^2 (m=5)`\n\t  since row and column are exchange-able logically in this case.\n\n5) we found that not all states are valid due to the constraint, e.g. RRB, GGB is invalid, so we can prune row\'s state as [3 choose 1, 2 choose 1, ... , 2 choose 1] , then number of states will become 3 * ( 2 ^ (m-1) ) \n\t- -> [state transitions]: ( 3 * ( 2 ^ (m-1) ) ) ^ 2\n\t- -> Total Time: `n*((3*(2^(m-1)))^2)`\n\t- ->  `n * ( 48^2 )` (m=5)\n\n6) observe  5)\'s states to see if there are any repeated patterns for reducing calculations\n```\n123\n---\nRGB\nRBG\nGRB\nGBR\nBRG\nBGR\n```\n  - when m=3, RGB, BGR, GRB seems the same pattern where 1st, 2nd, 3rd cell colors differs to each other, can be denoted as [123]. While RGR, GRG seems the same pattern where 1st, 3rd cell color are the same, denoted [121]. So that if we can prove each permutation of the same pattern has the same state transition, then we can safely calculate 1 permutation\'s state value(ways) and multiply by number of permutations to get total original ways.\n  The permutations of a pattern [123] can be calculated by replacing as color permutations\n  denoted as `P(|colors|, |pattern colors|)`, \nP(3,3)=6, when m >= 3\nP(3,2)=6, when m = 2\nP(3,1)=3, when m <= 1\n-> generalized as `P(3, min(3, m))`\n\n7) what about number of state transitions of each permutation of  a specific pattern? we found numbers are the same as well, since they are also permutations of same pattern state transitions, \ne.g. m=3,\n```\nrow=i       row=i-1\nBGR(123)    GBG(121)  GRB(123)  GRG(121)  RBG(123)      \nBRG(123)    GBR(123)  RBR(121)  RGB(123)  RGR(121)   \n```\n-  n_ways(row=i, state=[123]) = n_ways(row=i-1, state=[121])*2 + n_ways(row=i-1, state=[123])*2\n\n\n8) based on 6), number of pattern as state can be: when m=3, first 2 cells as [12], then 3rd cell can choose from {1,3} and result in [123], [121] \n  -> total number is 2 \n  -> generalize as `1* 1 * 2^(m-2)` = `2^(m-2)`\n\n9) based on 7), since we know row=i-1\'s number of pattern as state are also 2^(m-2), how do we find all state transitions as \n  `n_ways(row=i, state=way1) = n_ways(row=i-1, state=way1)*n1 + n_ways(row=i-1, state=way2)*n2 + ...`?\n  ```\nrow=i    row=i-1\n123      212(121)  231(123)  232(121)  312(123)   \n121      212(121)  213(123)  232(121)  312(123)  313(121)\n```\n- if we think from single row=i\'s pattern [123]\'s transitions from row=i-1 possible patterns [212], [232] can also generalized to [121], which means it has [121] * 2 transitions\n\t- "normalize" row=i-1 pattern as 1st cell as 1, 2nd cell as 2, rest cell as 3 (e.g. [231] -> 2:1, 3:2, 1:3 -> pattern:[123])\n\t- finally, we can get\n\t  `n_ways(row=i, state=[123]) = n_ways(row=i-1, state=[121])*2 + n_ways(row=i-1, state=[123])*2`\n\n10) base 8), 9), \n\t- -> [state transitions]: `( 2^(m-2) ) ^ 2`\n\t- -> Total Time: `n*((2^(m-2))^2)`\n\t- ->  `n * ( 8^2 )` (m=5)\n\n11) we can store row\'s state transitions function in advance, so for each row\'s state-value calculation we just reference that without re-calculation of state transitions\n\n12) since each state\'s element is m <= 5, additional compression by 3-base or 2-bit doesn\'t help much\n\n< code >\n```python\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        from functools import reduce\n        MOD = 10**9 + 7\n        sum_mod = lambda x,y: (x+y)%MOD\n        \n        def normalize(pat_var):\n            mapping = { e:i+1 for i, e in enumerate(pat_var[0:2]) }\n            mapping[list({1,2,3}.difference(mapping.keys()))[0]] = 3\n            return tuple([ mapping[e] for e in pat_var])\n        \n        def get_pats(m, i, pat, pats):\n            if i == m-1:\n                pats.append(tuple(pat))\n                return\n            i_nx = i+1\n            for p_it_nx in (1,2,3):\n                if (i_nx <= 1 and p_it_nx == i_nx+1 ) or (i_nx >= 2 and p_it_nx != pat[-1]):\n                    pat.append(p_it_nx)\n                    get_pats(m, i_nx, pat, pats)\n                    pat.pop()\n            return pats\n        \n        def get_trans(pat, i, pat_pre, trans):\n            if i == len(pat)-1:\n                pat_nl = normalize(pat_pre)\n                trans[pat_nl] = trans.get(pat_nl, 0) + 1\n                return\n            for p_it_pre in (1,2,3):\n                i_nx = i+1\n                if (p_it_pre != pat[i_nx]\n                    and (not pat_pre or p_it_pre != pat_pre[-1])):\n                    pat_pre.append(p_it_pre)\n                    get_trans(pat, i_nx, pat_pre, trans)\n                    pat_pre.pop()\n            return trans\n\n        pats = get_pats(m, -1, [], [])\n        # {pattern_i: {pattern_pre:count}}\n        pat_trans = { pat: get_trans(pat, -1, [], {}) for pat in pats }  \n        \n        p_counts = { pat:1 for pat in pat_trans.keys() }\n        for i in range(n-1):\n            p_counts_new = {}\n            for pat, trans in pat_trans.items():\n                p_counts_new[pat] = reduce(sum_mod, (p_counts[pat_pre] * cnt for pat_pre, cnt in trans.items()))\n            p_counts = p_counts_new\n        \n        res = reduce(sum_mod, (cnt for cnt in p_counts.values()))\n        perms = reduce(lambda x,y: x*y, (3-i for i in range(min(3,m))))\n        return (res * perms) % MOD\n```\n\n< reference >\n- https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/574943/Java-Detailed-Explanation-with-Graph-Demo-DP-Easy-Understand
['Dynamic Programming', 'Python']