Java Simple Column-by-Column DP Solution O(48^2*N)
For m = 5, there are at most 48 valid states for a single column so we can handle it column by column.\nWe encode the color arrangement by bit mask (3 bit for a
For m = 5, there are at most 48 valid states for a single column so we can handle it column by column.\nWe encode the color arrangement by bit mask (3 bit for a position) and use dfs to generate the all valid states.\nThen for each column, we iterator all the states and check if it\'s still valid with the previous column.\n```\nclass Solution {\n    static int mod = (int) 1e9 + 7;\n    public int colorTheGrid(int m, int n) {\n        Map<Integer, Long> state = new HashMap();\n        dfs(state, 0, m, -1, 0);\n        Set<Integer> set = new HashSet(state.keySet());\n        for (int i = 1; i < n; ++i) {\n            Map<Integer, Long> dp = new HashMap();\n            for (int a : set) {\n                for (int b : set) {\n                    if (0 == (a & b)) dp.put(a, (dp.getOrDefault(a, 0L) + state.get(b)) % mod);\n                }\n            }\n            state = dp;\n        }\n        long res = 0L;\n        for (long val : state.values()) res = (res + val) % mod;\n        return (int) res;\n    }\n    private void dfs(Map<Integer, Long> state, int j, int m, int prev, int cur) {\n        if (j == m) {\n            state.put(cur, state.getOrDefault(cur, 0L) + 1);\n            return;\n        }\n        for (int i = 0; i < 3; ++i) {\n            if (i == prev) continue;\n            dfs(state, j + 1, m, i, (cur << 3) | (1 << i));\n        }\n    }\n}\n```
[]