C++ | DP with Bitmask
Intuition\n Describe your first thoughts on how to solve this problem. \nMaximize the sum by greedily selecting the highest values, but it didn\'t work.\n-> use
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nMaximize the sum by greedily selecting the highest values, but it didn\'t work.\n-> use DP to get optimum value while ensuring unique row selections.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Flattening and sorting the grid:\n    * Flattening the 2D grid into a list of `{value, rowIdx}` pairs simplifies sorting and tracks each element by its row.\n    * We don\'t care about the column index.\n    * Sorting in descending order of value allows us to select the highest values first.\n2. DP and Bitmask optimization:\n    * We need DP to track the maximum sum for each combination of selected rows.\n    * Since the contraints are `N, M <= 10`, any subset of selected row combinations can be represented using a bitmask of length `M`\n    * For each value in the sorted list, update the DP array by iterating over all possible `mask` combinations.\n    * For each mask, add the current value\'s row to this combination: $$dp[new\\_mask]=max(dp[new\\_mask],dp[mask]+value)$$\n3. Handling Identical Values:\n    * values are sorted, so we can span a window of same value and process them together in one update (`dp = new_dp`)\n4. Get maximum sum in the DP array\n\n# Complexity\n- Time complexity: $$O(M\u22C5N\u22C52^M)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(M\u22C5N+2^M)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        using pii = pair<int, int>;\n        const auto m = grid.size(); // rows\n        const auto n = grid[0].size();\n        const auto mxn = m*n;\n        \n        auto nums = vector<pii>(mxn); // pair of {value, rowIdx}\n        for (auto i=0; i<m; ++i) {\n            for (auto j=0; j<n; ++j) {\n                nums[i*n+j] = {grid[i][j], i};\n            }\n        }\n        sort(nums.rbegin(), nums.rend()); // descending\n       \n        // storing which row has already been taken through a bitmask\n        // => 2^M = 1024 maximum (Acceptable)\n        // ==> dp[i] = maximum sum of the row combination i (bitwise)\n        const auto MASK_MAX = 1<<m;\n        auto dp = vector<int>(MASK_MAX);\n        dp[0] = 0;\n        auto l=0, r=0;\n        while (l < mxn) {\n            // span a [l, r) range of the same value\n            while (r < MN && nums[l].first == nums[r].first) ++r;\n            auto new_dp = dp;\n            for (auto mask = 0; mask < MASK_MAX; ++mask) {\n                for (auto i=l; i<r; ++i) {\n                    auto [val, rowIdx] = nums[i];\n                    // rowIdx already taken\n                    if ((mask >> rowIdx) & 1) continue;\n                    new_dp[mask|(1<<rowIdx)] = \n                        max(new_dp[mask|(1<<rowIdx)], dp[mask] + val);\n                }\n            }\n            dp = new_dp;\n            l = r;\n        }\n\n        return *max_element(dp.begin(), dp.end());\n    }\n};\n\n```
['C++']