[C++] DP
Similar to: 1411. Number of Ways to Paint N \xD7 3 Grid\n\n\n\nvector<string> moves;\nint MOD = 1e9 + 7;\nvoid fill(string s, int n, int p){\n    if(n==0){\n   
*Similar to*: [1411. Number of Ways to Paint N \xD7 3 Grid](https://leetcode.com/problems/number-of-ways-to-paint-n-3-grid/discuss/941091/c%2B%2Boror-Easy-to-understand-oror-DFS-%2B-Memorization-oror-Space-%3A-O(12n)-Time-%3AO(12n))\n\n```\n\nvector<string> moves;\nint MOD = 1e9 + 7;\nvoid fill(string s, int n, int p){\n    if(n==0){\n        moves.push_back(s);\n        return;\n    }\n    for(int i=1; i<4; i++){\n        if(p==i){\n            continue;\n        }\n        string m = to_string(i);\n        fill(s+m, n-1, i);\n    }\n    return;\n}\nclass Solution {\npublic:\n    vector<vector<int>>memo;\n    int solve(int n, int lastIdx, int m){\n        if (n == 0) return 1;\n        int ret = 0;\n        if (memo[n][lastIdx] != -1) return memo[n][lastIdx];\n        string last = moves[lastIdx];\n        for (int idx = 0; idx<moves.size(); idx++) {\n            string move = moves[idx];\n            bool same = false;\n            for (int i = 0; i < m; i++) if (move[i] == last[i]) same = true;   \n            if (!same) ret = (ret + solve(n - 1, idx, m)%MOD)%MOD;\n        }\n        return memo[n][lastIdx]= ret%MOD;\n    }\n    int colorTheGrid(int m, int n){\n        moves.clear();\n        fill("", m, -1);\n        //cout<<moves.size()<<endl;\n        memo.resize(n + 1, vector<int>(moves.size(), -1));\n        int ret = 0;\n        for (int idx = 0; idx < moves.size(); idx++)\n            ret =  (ret + solve(n-1, idx, m)%MOD)%MOD;\n        return ret;\n    }\n};\n\n```\n\n***UPVOTE\uD83D\uDC4D !!!***
['Dynamic Programming', 'C']