C++ Recursion + Memo
\nclass Solution {\npublic:\n    string color_scheme = "RYG";\n    int mod;\n    vector<string>valid_moves;\n    unordered_map<string,int>dp;\n    void generate
```\nclass Solution {\npublic:\n    string color_scheme = "RYG";\n    int mod;\n    vector<string>valid_moves;\n    unordered_map<string,int>dp;\n    void generateValidMoves(int n , int taken , char last, string &cur)\n    {   if(taken==n)\n        {valid_moves.push_back(cur);\n         return;\n        }\n        for(auto x : color_scheme)\n        {   if(last!=x)\n            {   cur.push_back(x);\n                generateValidMoves(n,taken+1,x,cur);\n                cur.pop_back();\n            }\n        }\n    }\n    int solve(int n , int cur_len,string last_move)\n    {\n        if(cur_len==n)return 1;\n        int ans =0;\n        string hash = to_string(cur_len)+"#"+last_move;\n        if(dp.find(hash)!=dp.end())return dp[hash];\n        for(int i =0;i<valid_moves.size();i++)\n        {\n            auto cur_move = valid_moves[i];\n            bool no_match =1;\n            for(int i =0;i<last_move.size();i++)\n            {\n                if(last_move[i]==cur_move[i])no_match=0;\n            }\n            if(no_match)\n            {\n                ans= (ans%mod+solve(n,cur_len+1,cur_move))%mod;\n            }\n        }\n        return dp[hash]= ans;\n    }\n    \n    int colorTheGrid(int m, int n) {\n        string cur ="";\n        generateValidMoves(m,0,\'Z\',cur);\n        string start = "";\n        for(int i =0;i<m;i++)start+="B";\n        mod=1e9+7;\n        return solve(n,0,start);\n        \n    }\n};\n```
[]