Space Optimized DP
Code\n\n#include <bits/stdc++.h>\n\n#define pb push_back\n#define po pop_back\n#include <string>\nusing namespace std;\n\ntemplate <typename T>\nstd::istream &o
# Code\n```\n#include <bits/stdc++.h>\n\n#define pb push_back\n#define po pop_back\n#include <string>\nusing namespace std;\n\ntemplate <typename T>\nstd::istream &operator>>(std::istream &in, std::vector<T> &v){for(int i =0;i<v.size();i++){in>>v[i];}return in;}\n\ntemplate <typename A, typename B>\nostream &operator<<(ostream &os, const pair<A, B> &p) { return os << \'(\' << p.first << ", " << p.second << \')\'; }\ntemplate <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>\nostream &operator<<(ostream &os, const T_container &v)\n{\n    os << \'{\';\n    string sep;\n    for (const T &x : v)\n        os << sep << x, sep = ", ";\n    return os << "}";\n}\nvoid dbg_out() { cerr << endl; }\ntemplate <typename Head, typename... Tail>\nvoid dbg_out(Head H, Tail... T)\n{\n    cerr << \' \' << H;\n    dbg_out(T...);\n}\n#ifdef LOCAL\n#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)\n#else\n#define dbg(...)\n#endif\n\n// #define ar array\n#define ll long long\n// #define ld long double\n// #define sza(x) ((int)x.size())\n#define all(a) (a).begin(), (a).end()\n\nclass Solution {\npublic:\n    bool iscompatible(vector<int>& a, vector<int>& b){\n        for(int i=0;i<a.size();i++){\n            if(a[i]==b[i]){\n                return false;\n            }\n        }\n        return true;\n    }\n    vector<vector<int>> gen(int n){\n        set<vector<int>>prev;\n        vector<int>b(n, -1);\n        prev.insert(b);\n        for(int i=0;i<n;i++){\n            set<vector<int>>cur;\n            for(auto j:prev){\n                vector<int>t=j;\n                for(int k=0;k<3;k++){\n                    if(i==0){\n                        t[i]=k;\n                    }else if(t[i-1]!=k){\n                        t[i]=k;\n                    }\n                    if(t[i]!=-1){\n                        cur.insert(t);\n                    }\n                }\n            }\n            prev=cur;\n        }\n        vector<vector<int>>ans;\n        for(auto i:prev){\n            ans.push_back(i);\n        }\n        return ans;\n    }\n    int colorTheGrid(int m, int n) {\n        long long mod=1e9 + 7;\n        vector<vector<int>>prev=gen(m);\n        map<vector<int>, long long>mprev;\n\n        for(auto i:prev){\n            mprev[i]++;\n        }\n\n        for(int i=1;i<n;i++){\n            vector<vector<int>>cur=prev;\n            map<vector<int>, long long>mcur;\n            for(int j=0;j<prev.size();j++){\n                for(int k=0;k<prev.size();k++){\n                    if(iscompatible(cur[j], prev[k])){\n                        mcur[cur[j]]=(mcur[cur[j]]+mprev[prev[k]])%mod;\n                    }\n                }\n            }\n            mprev=mcur;\n        }\n\n\n        int res=0;\n        for(auto i:mprev){\n            res=(res+i.second)%mod;\n        }\n\n        return res;\n\n\n    }\n};\n```
['Dynamic Programming', 'C++']