c++ | dp | graph
\nclass Solution {\npublic:\n    int md=1000000007;\n    vector<string> st;\n    int dp[50][1001];\n    void fill(int m,char prev,string s){\n        if(m==0)st
```\nclass Solution {\npublic:\n    int md=1000000007;\n    vector<string> st;\n    int dp[50][1001];\n    void fill(int m,char prev,string s){\n        if(m==0)st.push_back(s);\n        else{\n            string t="RGB";\n            for(auto&i:t){\n                if(i!=prev) fill(m-1,i,s+i);\n            }           \n        }\n        \n    }\n    int dfs(vector<vector<int>> &gr,int i,int n){\n        if(!n) return 1;\n        if(dp[i][n]!=-1) return dp[i][n];\n        int ans=0;\n        for(auto&j:gr[i]) ans=(ans%md+dfs(gr,j,n-1)%md)%md;\n        return dp[i][n]=ans%md;\n    }\n    int colorTheGrid(int m, int n) {\n        fill(m,\'#\',"");\n        memset(dp,-1,sizeof(dp));\n        int sz=st.size();\n        vector<vector<int>>gr(sz);\n        for(int i=0;i<sz;i++){\n            for(int j=i+1;j<sz;j++){                \n                bool f=false;\n                for(int k=0;k<m;k++){\n                    if(st[i][k]==st[j][k]){\n                        f=true;\n                        break;\n                    }\n                }\n                if(!f){\n                    gr[i].push_back(j);\n                    gr[j].push_back(i);\n                }\n            }\n        }\n        int ans=0;\n        for(int i=0;i<sz;i++) ans=(ans%md+dfs(gr,i,n-1)%md)%md;\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Graph', 'C']