Explained Solution
Approach\nWe are using integer as bit mask to pass which color have we used as we can only use 1,2,3 color .\n\n# Complexity\n- Time complexity: O(NM2^M*2)\n Ad
# Approach\nWe are using integer as bit mask to pass which color have we used as we can only use 1,2,3 color .\n\n# Complexity\n- Time complexity: O(N*M*2^M*2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    int dp[1001][1024] = {};\n    // i col(0,1,2,3..m-1) and j row(0,1,2,..n-1) cur is current column pattern and pr is previous column pattern\n    // we can have 4 states in every cell so 2 bits to define and to make full pattern if m = 5 then we will need 1024 bits\n    int solve(int i, int j, int m, int n, int cur, int pr){\n        if(j == n) return 1; // if we reach end row\n        if(i == 0 && dp[j][pr] != 0) return dp[j][pr]; // if we go for new row and column start at 0 so we check if we got previous state before or not\n        // Now we try to fill j, i place according to it\'s up and left side\n        // pr : 1 2 3 1 2\n        // cur: 2 3 \n        // above we can see we can only fill 1 here\n        int left = i == 0 ? 0 : (cur>>2*(i-1))&3; // here we see cur bits just left side \n        int up = j == 0? 0 : (pr>>(2*i))&3; // here we see upwards bits in pr\n        long int ans = 0;\n        // here we are trying to fill colors 1 or 2 or 3\n        for(int color = 1;color<=3;color++){\n            if(color != left && color != up){\n                if(i == m-1) ans += solve(0,j+1,m,n,0,(cur|(color<<(2*i))));\n                else ans += solve(i+1,j,m,n,(cur|(color<<(2*i))),pr);\n                ans = ans%(1000000007);  \n            }\n        }\n        if(i == 0) dp[j][pr] = ans; // if we got first col then reserve this state\n        return ans;\n    }\n    int colorTheGrid(int m, int n) {\n        return solve(0,0,m,n,0,0);\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Memoization', 'C++']