Top Down dp with bit masking Easy Complete Solution
My first thought was to just calculate No of possible paths to n-1, m-1 with given constrain but the thing went wrong was the other left remaining squires can f
My first thought was to just calculate No of possible paths to n-1, m-1 with given constrain but the thing went wrong was the other left remaining squires can form different combination which is not part of selected path so it failed  ``` :(```\n\nto colur any cell we need information about just upper sell and left cell``` ( if u plan to paint cells one after another sequencily from 0 to m-1th column till { 0 to row to n-1th row }  ) ```\n\nSo the hint here is the m<=5 means we can effectively store the previous row colours and start painting by looking upper cell colur and just left painted cell\'s colur with following the constrain.\n```  Okey !```\n\n``` \nSo now we can start from 0th row with prev row intialised with\n"##... m times " (means first row has no such ristrictions of upper cell)\n\'0\' => red \'1\' =blue \'2\' => green\n``` \n\nwhen we enter in solve function we call a help function which genrates all possible next states for next i+1 row (see the implimenation of help it\'s very basic)\nthen for each state we call solve(i+1, state_i) and add all the solutions.\nto memoize the recursion we can transform this string into 3 base number which will help in space optimization and easy access to solved subproblems with O(1) complexcity\n\n```       \n       i    s      next states\nTime : n* (3^m) * (3* 2^(m-1)) =>  n=no of rows,  3^m  string different values(all possible) , inner loop next states< (3*2^(m-1))   \n```\n```\nSpace : n* (3^m)\n```\n```\nclass Solution {\npublic:\n      \n    int m=1e9+7;\n    void help(string &s, string &t, vector<string> &a)  // genrates next all next possible arrangement for next row, max next states :3*2*2*2*2 -> 48 it will \n    {// very much less once we have upper cell and left cell contrain. 48 will only for 0th row \n    \n        if(t.size()==s.size())\n        {\n            a.push_back(t);\n            return ;\n        }\n        char p;\n        if(t.size()>0)\n        p= t.back();\n        else p=\'#\';\n        int k=t.size();\n        \n        for(int i=\'0\'; i<=\'2\'; i++)\n        {\n            if(p!=i && s[k]!=i)\n            {\n                t.push_back(i);\n                help(s,t,a);\n                t.pop_back();\n            }\n        }\n        \n        return;\n    }\n    \n\n    // map<pair<int,string>, int> mp;\n\n     int n;\n     int dp[1001][244];\n    \n    int change(string &s)  // string to 3 based number for easy storage\n    {\n        if(s.back()==\'#\') return 0;\n        int n=0;\n        for(auto i: s) n=3*n+(i-\'0\');\n        return n;\n    }\n              //curr row      prev state  \n    int solve(   int i,       string &u )\n    {\n        if(i==n) return 1;\n        \n        // if(mp.find({i,u})!=mp.end()) return mp[{i,u}];\n        \n        int num= change(u);\n        if(dp[i][num]!=-1) return dp[i][num];\n        \n        vector<string>a;\n        string t="";\n        help(u,t, a);\n        long long ans=0;\n        for(auto k: a) // at max (in i=0 ) 48 calls\n        {\n            ans+=solve(i+1, k)%m;\n            ans%=m;\n        }\n            \n        // return mp[{i,u}]=ans;\n        \n        return dp[i][num]=ans;\n        \n        \n        \n    }\n    \n    int colorTheGrid(int m, int n1) \n    {\n        // m=m1;\n        n=n1;\n        string s="";\n        while(m--) s+=\'#\';\n        memset(dp,-1,sizeof(dp));\n\t\t// s can have at max 48 different values for any row \n        return solve(0,s);\n    }\n};\n\n\n// ignore  \n// my first approach to problem\n// possible path with constrain to reach destination  \n//     int mo= 1e9+7;\n//     int dp[6][1001][4][4];\n//     int n; int m;\n//     int solve(int i, int j, int l, int u)\n//     {\n//         if(i==n-1 && j==m-1) \n//         {\n            \n//             int t=0;\n//             for(int c=0; c<=2; c++) if(c!=l && c!=u) t++;\n//             return t;\n//         }\n        \n//         if(i>=n || j>=m) return 0;\n        \n//         if(dp[i][j][l+1][u+1]!=-1) return  dp[i][j][l+1][u+1];\n//         long long ans=0;\n//         for(int c=0; c<=2; c++)\n//         {\n//             if(c!=l && c!=u)\n//             {\n//                 //down\n//                 ans+=solve(i+1,j,l,c);\n//                 //right\n//                 // ans%=mo;\n//                 ans+=solve(i, j+1,c,u);\n//                 // ans%=mo;\n//             }\n//         }\n//         return dp[i][j][l+1][u+1]=ans;        \n        \n//     }\n    \n\n```\n\n\n\n\n\n\n\n\n\n\n\n
['Dynamic Programming', 'Recursion', 'C', 'Bitmask']