BY USING PREDEFINED STRING WITH ADJACENT MATRIX WITH DP.
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```cpp []\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n\n    void generateValidRows(vector<string>& validRows, int m, int i, string s) {\n        if (i == m) {\n            validRows.push_back(s);\n            return;\n        }\n        for (char color = \'0\'; color <= \'2\'; ++color) {\n            if (i == 0 || s[i - 1] != color) {\n                generateValidRows(validRows, m, i + 1, s + color);\n            }\n        }\n    }\n\n    int colorTheGrid(int m, int n) {\n        vector<string> validRows;\n        generateValidRows(validRows, m, 0, "");\n        int rowCount = validRows.size();\n\n        // Create adjacency list\n        vector<vector<int>> adj(rowCount);\n        for (int i = 0; i < rowCount; ++i) {\n            for (int j = 0; j < rowCount; ++j) {\n                bool canPlace = true;\n                for (int k = 0; k < m; ++k) {\n                    if (validRows[i][k] == validRows[j][k]) {\n                        canPlace = false;\n                        break;\n                    }\n                }\n                if (canPlace) {\n                    adj[i].push_back(j);\n                }\n            }\n        }\n\n        // dp table to store the number of ways to paint the grid up to the current column\n        vector<int> dp(rowCount, 1);\n\n        // Fill dp table\n        for (int col = 1; col < n; ++col) {\n            vector<int> newDp(rowCount, 0);\n            for (int i = 0; i < rowCount; ++i) {\n                for (int j : adj[i]) {\n                    newDp[j] = (newDp[j] + dp[i]) % mod;\n                }\n            }\n            dp = newDp;\n        }\n\n        int count = 0;\n        for (int i = 0; i < rowCount; ++i) {\n            count = (count + dp[i]) % mod;\n        }\n        return count;\n    }\n};
['Dynamic Programming', 'C++']