Bottom-Up DP solution, beats 98% of cpp solutions
Beats 98.05% in Time and 99.35% in Space for cpp solutions\n\n\n\nclass Solution {\npublic:\n    const int MOD = 1e9 + 7;\n    void generateRows(vector<int> &ro
Beats **98.05%** in Time and **99.35%** in Space for cpp solutions\n![image](https://assets.leetcode.com/users/images/775029c7-7c97-4a8c-a93a-a718a67fe0f1_1658343994.58358.png)\n\n```\nclass Solution {\npublic:\n    const int MOD = 1e9 + 7;\n    void generateRows(vector<int> &rows, int idx, int row, int last, int &M){\n        if(idx == M){\n            rows.push_back(row);\n            return;\n        }\n        for(int i = 0;i<3;i++){\n            if(idx == 0 || last != i)\n                generateRows(rows, idx + 1, row * 10 + i, i, M);\n        }\n    }\n    bool can(vector<int> &rows, int i, int j, int M){\n        int rowi = rows[i], rowj = rows[j];\n        while(M--){\n            if(rowi % 10 == rowj %10)\n                return 0;\n            rowi /= 10; rowj /=10;\n        }\n        return 1;\n    }\n    void generateMoves(vector<int> &rows, vector<vector<int> > &Moves, int &m){\n        int X = rows.size();\n        for(int i = 0;i<X;i++){\n            for(int j = 0;j < X;j++){\n                if(i == j)continue;\n                if(can(rows, i, j, m))\n                    Moves[i].push_back(j);\n            }\n        }\n    }\n    int colorTheGrid(int m, int N) {\n    // Time: O(9^m + N * 3^m)\n        vector< int > rows;\n        generateRows(rows, 0, 0, 0, m);\n        int X = rows.size();\n        vector< vector<int> >Moves(X, vector<int>());\n        generateMoves(rows, Moves, m);\n        \n        int dp[2][X];\n        // Base case\n        for(int i = 0;i<X;i++)\n            dp[0][i] = 1;\n        \n        for(int idx = 1;idx<N;idx++){\n            for(int lastRow = 0;lastRow<X;lastRow++){\n                dp[idx&1][lastRow] = 0;\n                for(int &i: Moves[lastRow]){\n                    dp[idx&1][lastRow] += dp[idx&1^1][i];\n                    dp[idx&1][lastRow] %= MOD;\n                }\n            }\n        }\n        \n        int ans = 0;\n        for(int i = 0;i<X;i++){\n            ans += dp[N&1^1][i];\n            ans %= MOD;\n        }\n        return ans;\n    }\n};\n```\n\n
['Dynamic Programming']