2 Bitmask + Dp solution
Intuition\n Describe your first thoughts on how to solve this problem. \nNote the memoisation. To reduce the memory usage we only memoise the i and premask as a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nNote the memoisation. To reduce the memory usage we only memoise the i and premask as at j = 0, it is obvious that curmask should be zero.\n\n2 bits represents colors - \n00 -> while\n01 -> red\n10 -> yellow\n11 -> blue\n\nTo identify the prevous color and previous row color you have to analyse 2 bit at a time. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    int dp[1001][1<<10];\n    int solve(int i, int j, int premask, int curmask, int n, int m){\n        if(i == n) return 1;\n        if(dp[i][premask]!=-1 && j == 0) return dp[i][premask];\n        if(j == m) return solve(i + 1, 0, curmask, 0, n, m);\n        long long ans = 0;\n        for(int k = 1; k<=3; k++){\n            if(((premask>>(2*j))&3) != k && (j == 0 || ((curmask>>(2*j-2))&3) != k)){\n                ans += solve(i, j+1, premask, curmask | (k<<(2*j)), n, m);\n                ans = ans%mod;\n            }\n        }\n        if(j == 0) dp[i][premask] = ans;\n        return ans;\n    }\n    int colorTheGrid(int m, int n) {\n        memset(dp, -1, sizeof(dp));\n        return solve(0, 0, 0, 0, n, m);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Bitmask', 'C++']