Java | Short DP (bottom-up)
Ideas\nEach column is a state, with 3^5 possible states; however, there are a lot of invalid states and base 3 is difficult to handle, so we will use 2^10, 2 bi
#### Ideas\nEach column is a state, with `3^5` possible states; however, there are a lot of invalid states and base 3 is difficult to handle, so we will use `2^10`, 2 bits each to represent it. Here I\'ve chosen `00 to be invalid, and 01 -> blue, 10 -> red, 11 -> green.`\n\nThen for each configuration, we check previous configuration, then sum them up.\n#### Steps\n1. Write a `ok(a, b, m)` function that compares whether `a` and `b` shares the same 2 bits for length `2*m`.\n2. The base case is 1 when `ok(a, a>>2,m-1)` return true, 0 when false.\n3. The recurring relationship is when `ok(a,b,m)` return true and then add it up.\n\n#### Time Complexity: Worst case (48 * 2^M * N)\nThe reason for 48 is because there are at most 48 valid states for `M=5`.\n\n#### Thoughts\nYes, we can have optimized it by only travesing the valid states, but it is unncessary for getting AC.\n```Java\nclass Solution {\n    public int colorTheGrid(int m, int n) {\n        int A = 1 << 2*m, M = (int)1e9+7;\n        int[] dp = new int[A];\n        for (int i = 1; i < A; i++){\n            if (ok(i,i>>2,m-1)){ // base case\n                dp[i]=1;\n            }\n        }\n        for (int i = 1; i < n; i++){\n            int[] next = new int[A];\n            for (int j = 0; j < A; j++){\n                for (int k = 0; k < A && dp[j]>0; k++){\n                    if (dp[k]>0&&ok(k,j,m)){\n                        next[j]+=dp[k];\n                        next[j]%=M;\n                    }\n                }\n            }\n            dp=next;\n        }\n        return (int)(Arrays.stream(dp).asLongStream().sum()%M);\n    }\n\n    private boolean ok(int a, int b, int m){\n        for (int i = 0; i < m; i++, a/=4, b/=4){\n            if (a%4==0||b%4==0||a%4==b%4){\n                return false;\n            }\n        }\n        return true;\n    }\n}\n```
['Dynamic Programming', 'Java']