DP C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    class State {\n    public:\n        State (int row) : hash_value(1 << row) {\n            for (int i = 0; i < 10; ++i)\n                rows[i] = false;\n            rows[row] = true;\n        }\n        State add (int row) const {\n            State copy = *this;\n            copy.rows[row] = true;\n            copy.hash_value += (1 << row);\n            return copy;\n        }\n        bool is_valid (int row) const {\n            return !rows[row];\n        }\n\n        void print (int max) const {\n            cout << "   " ;\n            for (int i = 0; i < max; ++i) {\n                cout << rows[i] << " ";\n            }\n            cout << endl;\n        }\n        State (const State& s) : hash_value (s.hash_value) {\n            for (int i = 0; i < 10; ++i)\n                rows[i] = s.rows[i];\n        }\n        State () : hash_value(0) {\n            for (int i = 0; i < 10; ++i)\n                rows[i] = false;\n        }\n        // True if row is set, false otherwise\n        array<bool, 10> rows;\n        int hash_value = 0;\n        \n    };\n    struct StateHasher {\n        size_t operator()(const State& state) const {\n            return hash<int>()(state.hash_value);\n        }\n    };\n    struct StateEqual {\n        bool operator()(const State& lhs, const State& rhs) const {\n            return lhs.hash_value == rhs.hash_value;\n        }\n    };\n    typedef unordered_map<State, int, StateHasher, StateEqual> AllState;\n\n    int maxScore(vector<vector<int>>& grid) {\n        const int m = grid.size(), n = grid[0].size();\n\n        // vector<pair<int,int> > indices;\n        // for (int i = 0; i < m; ++i)\n        //     for (int j = 0; j < n; ++j)\n        //         indices.push_back({i,j});\n\n        // sort (indices.begin(), indices.end(), [&grid](pair<int,int> &a, pair<int,int> &b) {\n        //     return grid[a.first][a.second] < grid[b.first][b.second];\n        // });\n        map<int, unordered_set<int> > valToRows;\n        \n        for (int i = 0; i < m; ++i) {\n            for (int j = 0; j < n; ++j) {\n                const int val = grid[i][j];                \n                valToRows[val].insert(i);\n            }\n        }\n\n        vector<vector<vector<State> > > comb;\n        \n        for (int i = 0; i < m; ++i) {\n            comb.emplace_back(i + 1);\n            for (int k = 0; k <= i; ++k) {\n                if (i > k) {\n                    for (auto &state : comb[i - 1][k])\n                        comb[i][k].push_back(state);\n                }\n                if (k != 0) {\n                    for (auto &state : comb[i - 1][k - 1]) {\n                        comb[i][k].emplace_back(state.add(i));\n                    }\n                } else {\n                    comb[i][k].emplace_back(i);\n                }\n            }\n        }\n        // for (int i = 0; i < comb[m - 1].size(); ++i) {\n        //     cout << "choose " << i + 1 << ": " << endl;\n        //     for (auto &s : comb[m - 1][i])\n        //         s.print(m);\n        // }\n        \n        vector<AllState> dp(1);\n        for (auto k : comb[m - 1])\n            for (auto &s : k) {\n                dp[0].emplace(make_pair(s, 0));\n            }\n        dp[0].emplace(make_pair(State(), 0));\n        int last = 0;\n\n        for (auto &p : valToRows) {\n            // cout << endl << p.first << endl;\n            // for (auto s : p.second) cout << s << " ";\n            // cout << endl;\n            const int val = p.first;\n            const unordered_set<int>& rows = p.second;\n            AllState copy = dp[last];\n            for (auto &statePair : copy) {\n                const State &state = statePair.first;\n                int max = dp[last][state];\n                for (auto row : rows) {\n                    if (state.is_valid(row)) {\n                        const State nextState = state.add(row);\n                        const int score = val + dp[last][nextState];\n                        if (score > max) max = score;\n                    }\n                }\n                // cout << "state = " << state.hash_value << " " << max << endl;\n                // cout << max << " ";\n                statePair.second = max;\n            }\n\n            dp.emplace_back(move(copy));\n            last++;\n        }\n        const State start; \n        return dp[last][start];\n    }\n};\n\n/*\nGenerate all combinations subroutine:\n    1. Let C(n, k) = all ways to choose k from rows [0: n]\n        = Multiplex(A[n], C(n - 1, k - 1))\n            concat with, if n >= k, C(n - 1, k) .\n    \n    We always want to select the highest value, if possible. It may not be possible because of the row restrictions.\n\n    Backtracking with memoization?\n        - choose an element, mark that row as unchooseable, \n        - move on to the next element\n\n    Define state = unordered_set<int>\n    Define Valid (r, state) = r not in state\n\n    1. Map val to a vector of rows\n\n    max_score (val, state) :\n        let rows = the collection of rows that contains val\n        let nextVal = the next value in the grid such that nextVal < val\n\n        Let F be a function that maps rows to a score:\n            if row is valid in state, then\n                let state\' = mutate(state, row)\n                return val + max_score(nextVal, state\')\n            else return max_score(nextVal, state)\n\n        return the max_element F(rows)\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n*/\n```
['C++']