1931 Backtrack with memo | DP row by row
Solution 1: simple backtrack\n2D dp -> 1D dp -> string (string is hashable(cached) while list is not)\nm is no more than 5, so let m be 1D dp dimension\n\ndef c
# Solution 1: simple backtrack\n2D dp -> 1D dp -> string (string is hashable(cached) while list is not)\nm is no more than 5, so let m be 1D dp dimension\n```\ndef colorTheGrid(self, m: int, n: int) -> int:\n\t@lru_cache(None)\n\tdef backtrack(k=0, dp="0" * (m + 1)):\n\t\tif k == m * n: return 1\n\t\ti, j = divmod(k, m)\n\t\tres = 0\n\t\tfor color in {"1", "2", "3"} - {dp[j], dp[j-1]}:\n\t\t\tnew_dp = dp[:j] + color + dp[j+1:]\n\t\t\tres += backtrack(k+1, new_dp)\n\t\t\tres %= 10**9 + 7\n\t\treturn res\n\n\treturn backtrack()\n```\nimplement cache myself\n```\ndef colorTheGrid(self, m: int, n: int) -> int:\n    cache = {}\n    def backtrack(k=0, dp="0" * (m + 1)):\n        if (k, dp) not in cache:\n            if k == m * n: return 1\n            i, j = divmod(k, m)\n            res = 0\n            for color in {"1", "2", "3"} - {dp[j], dp[j-1]}:\n                new_dp = dp[:j] + color + dp[j+1:]\n                res += backtrack(k+1, new_dp)\n                res %= 10**9 + 7\n            cache[(k, dp)] = res\n        return cache[(k, dp)]\n\n    return backtrack()\n```\n# Solution 2: DP\n```\ndef colorTheGrid(self, m: int, n: int) -> int:\n    def backtrack(pre, i=0, cur=["0"]*(m+1), curs=set()):\n        # input: color pattern of the previous row\n        # output: set of possible color patterns of the current row\n        if i == m: return curs.add("".join(cur))\n        for color in {"1", "2", "3"} - {pre[i], cur[i-1]}:\n            cur[i] = color\n            backtrack(pre, i+1, cur, curs)\n\n    cache = collections.defaultdict(set)  # to better the backtrack above\n    pre_dp = {"0"*(m+1): 1}  # possible color patterns of previous row with counts\n    for _ in range(n):\n        dp = collections.defaultdict(int)\n        for pre, cnt in pre_dp.items():\n            if pre not in cache:\n                backtrack(pre, curs=cache[pre])\n            for cur in cache[pre]:\n                dp[cur] += cnt\n                dp[cur] %= 10**9 + 7\n        pre_dp = dp\n    return sum(pre_dp.values()) % (10**9 + 7)\n```\n\n
[]