DP with bitmask, similar to Prob 1349 Maximum Student Taking Exam
Consider each column, since it has much less valid states as compared to each row.\nThe below algorithm can also be extended to work for more than 3 colors scen
Consider each column, since it has much less valid states as compared to each row.\nThe below algorithm can also be extended to work for more than 3 colors scenario\n\n```\nclass Solution {    \n    long[] mask;\n    int idx = 0;\n    // RRR => 001001001, RGR => 001010001, RGB => 001010100\n    public int colorTheGrid(int m, int n) {\n\t    int K = 3;  // Three colors in total\n        int count = K;\n        for (int i=0; i<m-1; ++i)\n            count *= K;\n        mask = new long[count];\n        getMasks(0, m, K);\n        \n        // only consider valid mask value, neighbors do not have the samecolor\n        boolean[] valid = new boolean[count];\n        for (int i=0; i<count; ++i) {\n            if ((mask[i] & (mask[i] << K)) == 0) {\n                valid[i] = true;\n            }\n        }\n        \n        long[] dp = new long[count];\n        for (int i=0; i<count; ++i) {\n            dp[i] = valid[i] ? 1 : 0;\n        }\n        \n        long mod = (long) (1e9+7);\n        for (int i=1; i<=n-1; ++i) {\n            // for each column\n            long[] newDp = new long[count];\n            for (int j=0; j<count; ++j) {\n                if (valid[j]) {\n                    for (int k=0; k<count; ++k) {\n                        // each valid pairs of masks\n                        if (valid[k] && (mask[j] & mask[k]) == 0) {\n                            // if there is no "conflict"\n                            newDp[j] += dp[k];\n                        }\n                    }\n                    newDp[j] %= mod;\n                }\n            }\n            dp = newDp;\n        }\n        long sum = 0;\n        for (int i=0; i<count; ++i) {\n            sum += dp[i];\n        }\n        return (int) (sum % mod);\n    }\n    \n    void getMasks(long val, int m, int k) {\n        if (m == 0) {\n            mask[idx++] = val;\n            return;\n        }\n        for (int i=0; i<k; ++i) {\n            getMasks((val << k) | (1 << i), m-1, k);\n        }\n    }\n}\n```
['Dynamic Programming', 'Bitmask']