[Python] Simple Top-down DP explained
As each column is at most 5 colours high, then we process them column by column. We simply try all combinations and keep processing the ones that do not share a
As each column is at most 5 colours high, then we process them column by column. We simply try all combinations and keep processing the ones that do not share any colour with the previous column. \n\nThe trick is to use bit mask. We can label the 3 colours as `1`, `2`, `4`, which in binary form is `001`, `010`, `100`. So when we do an and operation between two columns, we know the condition is satisfied if the and operation gives me 0. For example, column 1 has colour `001 010 100`, then column 2 can have colours `010 100 001` or `010 100 010` etc.\n\n```python\nclass Solution:\n    def colorTheGrid(self, m: int, n: int) -> int:\n        MOD = 10**9 + 7\n        def generateColumn(prev, count): # find all possible column colour combinations\n            if count == m: return [0]\n            columns = []\n            for colour in (1, 2, 4):\n                if colour == prev: continue\n                for suffix in generateColumn(colour, count + 1):\n                    columns.append((colour << count * 3) | suffix) # count * 3 because each colour has 3 bits\n            return columns\n        possibleColumns = generateColumn(0, 0) \n        \n        @lru_cache(None)\n        def dfs(prevColumn, columnIndex):\n            if columnIndex >= n: return 1\n            res = 0\n            for column in possibleColumns:\n                if prevColumn & column: continue\n                res = (res + dfs(column, columnIndex + 1)) % MOD\n            return res\n        return dfs(0, 0)\n```
[]