(C++) DP, Bitmask (Base 3) - Commented code for better understandability
Learnt DP with bitmasking yesterday and it feels good to have solved this problem today :)\n\nclass Solution {\npublic:\n    int M, N;\n    int MOD = 1e9 + 7;\n
Learnt DP with bitmasking yesterday and it feels good to have solved this problem today :)\n```\nclass Solution {\npublic:\n    int M, N;\n    int MOD = 1e9 + 7;\n    \n    // function to fetch the (M-b-1)th bit of the mask with base 3\n    int isEqual(int a, int b, int x)\n    {\n        if(a == -1)\n            return false;\n        for(int i=0;i<(M-b-1);i++)\n            a = a/3;\n        return a%3 == x;\n    }\n    \n    void generate_masks(int prevMask, int currMask, int i, vector<int> &currMasks)\n    {\n        // if we have reached the end of row, store the current mask calculated and then backtrack.\n        if(i == M)\n        {\n            currMasks.push_back(currMask);\n            return;\n        }\n        \n        // The 1st if condition (isEqual call) is to ensure grid[i][j] != grid[i][j-1]\n        // The 2nd if condition (currMask%3) is to ensure grid[i][j] != grid[i-1][j]\n        \n        // assign red -> 0\n        if(!isEqual(prevMask,i,0) && (i == 0 || currMask%3 != 0))\n            generate_masks(prevMask, currMask*3, i+1, currMasks);\n            \n        // assign green -> 1\n        if(!isEqual(prevMask,i,1) && (i == 0 || currMask%3 != 1))\n            generate_masks(prevMask, currMask*3+1, i+1, currMasks);\n            \n        // assign blue -> 2\n        if(!isEqual(prevMask,i,2) && (i == 0 || currMask%3 != 2))\n            generate_masks(prevMask, currMask*3+2, i+1, currMasks);\n    }\n\n    int fun(vector<int> currMasks, int j, vector<vector<int>> &dp1, vector<vector<int>> &dp2)\n    {\n        // reached end of columns\n        if(j == N)\n            return 1;\n        \n        long long int ans = 0;\n        for(int i=0;i<currMasks.size();i++)\n        {\n            int mask = currMasks[i];\n            // if the current (j,mask) pair is already present in the dp, use it\n            if(dp1[j][mask])\n            {\n                dp1[j][mask] = dp1[j][mask];\n            }\n            // if the current mask\'s next set of masks are already present in the dp, use it\n            else if(dp2[mask].size())\n            {\n                dp1[j][mask] = fun(dp2[mask], j+1, dp1, dp2);\n            }\n            // else generate the next column\'s masks and calculate the answer recursively\n            else\n            {\n                vector<int> nextMasks;\n                generate_masks(mask, 0, 0, nextMasks);\n                dp2[mask] = nextMasks;\n\n                dp1[j][mask] = fun(nextMasks, j+1, dp1, dp2);\n            }\n            // answer for the current column till the end is the sum of: dp1[a][0] to dp1[a][242]\n            ans = (ans + dp1[j][mask]) % MOD;\n        }\n        return ans;\n    }\n    \n    int colorTheGrid(int m, int n) {\n        vector<int> currMasks;\n        M = m; N = n;\n        \n        // dp1[a][b] stores the number of possible combinations for column a and mask b. Our answer will be the sum of: dp1[a][0] to dp1[a][242].\n        vector<vector<int>> dp1(N, vector<int>(243));\n        \n        // dp2 is being used to avoid multiple calculations for following cases:\n        // if column A has a bitmask M, then column A+1 will always have the same number of possible bitmasks. We can calculate all of them at once and store them in dp2[M].\n        vector<vector<int>> dp2(243, vector<int>());\n        \n        // generate all possible bitmasks for column 1\n        generate_masks(-1, 0, 0, currMasks);\n        \n        return fun(currMasks, 0, dp1, dp2);\n    }\n};\n```\nPlease feel free to drop any questions or suggestions in the comments.\n\nTrying to figure out the time complexity but finding it a bit difficult right now. Any help is appreciated!
[]