Dynamic programming | Top to bottom | Easy to understand code
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\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 = 1000000007;\n    vector<int> getAllPossibleMasks(int prevMask, int m) {\n        vector<int> allPossibleMasks;\n        dfs(0, prevMask, 0, m, allPossibleMasks);\n        return allPossibleMasks;\n    }\n\n    void dfs(int row, int prevMask, int currentColMask, int m, vector<int>&allPossibleMasks) {\n         if(row == m) { \n             allPossibleMasks.push_back(currentColMask);\n             return;\n         } \n         for(int i=1; i<=3; i++) {\n             if((getColor(row, prevMask) != i ) && (row == 0 || getColor(row-1, currentColMask) != i)) {\n                 dfs(row + 1, prevMask, setCurrentColMask(currentColMask, row, i), m, allPossibleMasks);\n             }\n         }\n    }\n\n    int getColor(int row, int prevMask) {\n        //cout << prevMask << " " << row << endl;\n        return (prevMask >> (2*row)) & 3;\n    }\n\n     int setCurrentColMask(int mask, int pos, int color){\n        return mask | (color << (2*pos));\n    }\n\n\n    int getResult(int col, int m, int n, int prevMask, vector<vector<int> > &dp) {\n        if(col == n) {\n            return 1;\n        }\n\n        if(dp[col][prevMask] != -1) {\n            return dp[col][prevMask];\n        }\n        int ans = 0;\n\n        vector<int> allPossibleMasks = getAllPossibleMasks(prevMask, m);\n        for(int mask : allPossibleMasks) {\n            ans = (ans + getResult(col + 1, m, n, mask, dp))%mod;\n        }\n\n        dp[col][prevMask] = ans;\n\n        return ans;\n    }\n\n    int colorTheGrid(int m, int n) {\n        vector<vector<int> > dp(n+1, vector<int>(1025, -1));\n        return getResult(0, m, n, 0, dp);\n    }\n};\n```
['C++']