dp state compression, very similar to 1411
State compression;\n\nThis questions is very similar to the 1411\tNumber of Ways to Paint N \xD7 3 Grid    .\n\n1, First we rotate the grid 90 degree clockwise,
State compression;\n\nThis questions is very similar to the 1411\tNumber of Ways to Paint N \xD7 3 Grid    .\n\n1, First we rotate the grid 90 degree clockwise, now it became the harder version of 1411, that is N X M Grid (M is in the range [1-5])\n2, we use a 3-based number to represent the state of one row. For example, 210 = 2 * 3^2 + 1 * 3^1 + 0 * 3^0. Let\u2019s assume 0- red, 1-blue, 2-green.\n3, selfOK() is used to check whether one row is valid or not\n4, crossOK() is used to check the adjacent two rows.\n\n\n\n```\n   \n    int m ;\n    public int colorTheGrid(int M, int n) {\n        m = M;\n        \n        int mod = (int)(1e9 + 7);\n        \n        int x = (int)Math.pow(3, m);\n        int[][] dp = new int[n][x];  // dp[i][j] means the number of ways to color the grid when the i_th row is state j\n        \n        boolean[] f = new boolean[x];  // There are at most x =  3^m states\n        boolean[][] A= new boolean[x][x]; // Chceck the adjacent two rows. For example, the fist row is state p, the second row is state q\n\t\t\n\t\t\n        // preprocess all 3^m states;\n        for(int i = 0; i < x; i++){\n            if(selfOK(i)){\n                f[i] = true;\n            }\n        }\n        \n\t\t\n\t\t// preprocess all adjacent two rows\n        for(int i = 0; i < x; i++){\n            for(int j = 0; j < x; j++){\n                if(f[i]&& f[j] && crossOK(i, j)){\n                    A[i][j] = true;\n                }\n            }\n        }\n        \n  \n        \n        for(int i = 0; i < x; i++){\n            \n            if(f[i])\n                 dp[0][i] = 1;\n        }\n        \n        for(int i = 1;  i < n; i++){\n            \n            for(int p= 0; p <x; p++){\n                // if current row p is not valid, continue;\n                if(!f[p]) continue;\n                for(int q = 0; q < x; q++){\n                    // the previous row is q, if q is not valid, continue;\n                    if(!f[q]) continue;\n                    if(A[p][q]){ // if row p and row q are both valid, we update dp[i][p]\n                        dp[i][p] = (dp[i][p] +  dp[i - 1][q])%mod;\n                    }\n                    \n                }\n            }\n        }\n        \n        \n        int cnt = 0;\n        for(int p = 0; p <x; p++){\n            cnt = (cnt +  dp[n - 1][p])%mod;\n        }\n        return cnt;\n    }\n    \n    \n    \n    \n    //check one row is valid or not\n    boolean selfOK(int p){\n        int[] A = new int[m];\n        int idx = 0;\n        while(p >0){\n            A[idx] = p%3;\n            p /= 3;\n            idx++;\n        }\n        \n\t\t// if two adjacent colors are the same in the same row, that is invalid\n        for(int i = 0; i < m - 1; i++){\n            if(A[i] == A[i +1]) return false;\n        }\n         \n        return true;\n    }\n    \n    // check the adjacent two rows are valid or not\n    boolean crossOK(int p, int q){\n        int[] A = new int[m];\n        int[] B = new int[m];\n        \n        int idx = 0;\n        while(p >0){\n            A[idx] = p%3;\n            p /= 3;\n            idx++;\n        }\n        \n        \n        idx = 0;\n        while(q >0){\n            B[idx] = q%3;\n            q /= 3;\n            idx++;\n        }\n        \n\t\t// if the i_th color in the upper row is the same with the i_th color in the current row, that is invalid\n        for(int i = 0; i < m; i++){\n             \n            if(A[i] == B[i]) return false;\n        }\n        \n        return true;\n\n    }\n```
[]