C++ || DP || Memoization || Bitmasking || Sorting
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires selecting the maximum possible sum of unique values from different
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires selecting the maximum possible sum of unique values from different rows in a 2D grid. Since the number of rows is limited, we can utilize dynamic programming with a bitmask to keep track of the rows from which cells have been selected. By sorting the cells based on their values in descending order, we can attempt to maximize the sum by choosing the largest possible values first.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tData Preparation:\n\t\u2022\tConvert the grid into a list of cells where each cell is represented as a vector containing its value, row index, and column index.\n\t\u2022\tSort this list in descending order based on the cell values.\n2.\tDynamic Programming with Bitmasking:\n\t\u2022\tDefine a recursive function f(ind, mask) where:\n\t\u2022\tind is the current index in the sorted list of cells.\n\t\u2022\tmask is a bitmask representing the rows from which we have already selected a cell.\n\t\u2022\tIf the current cell\u2019s row has already been used (mask), skip to the next cell.\n\t\u2022\tOtherwise, consider two possibilities:\n\t1.\tInclude the Current Cell: Add its value to the sum and update the mask to mark the row as used.\n\t2.\tExclude the Current Cell: Move to the next cell without updating the mask.\n\t\u2022\tUse memoization to store and reuse results of subproblems.\n3.\tFinal Result:\n\t\u2022\tThe result is obtained by calling the recursive function with the initial index 0 and an empty mask 0.\n\n# Complexity\n- Time complexity: $$O(N * 2^m)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N * 2^m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    int m, n, N;\n    vector<vector<int>> mat;\n    map<pair<int,int>,int> dp;\nprivate:\n    int f(int ind, int mask){\n        if(ind == N) return 0;\n        if(dp.find({ind,mask})!=dp.end()) return dp[{ind,mask}];\n\n        int ans = 0;\n        int row = mat[ind][1];\n\n        if((1<<row) & mask) ans += f(ind+1,mask);\n        else{\n            int i = ind;\n            while(i<N && mat[ind][0] == mat[i][0])\n                i++;\n\n            int ans1 = mat[ind][0] + f(i,mask|(1<<row));\n            int ans2 = f(ind+1,mask);\n\n            ans = max(ans1, ans2);\n        }\n\n        return dp[{ind,mask}] = ans;\n    }\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        dp.clear();\n        mat.clear();\n        m = grid.size(), n = grid[0].size();\n        for(int i=0; i<m; i++){\n            for(int j=0; j<n; j++){\n                mat.push_back({grid[i][j],i,j});\n            }\n        }\n        N = mat.size();\n        sort(mat.begin(), mat.end(), greater<vector<int>>());\n\n        return f(0,0);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Sorting', 'Bitmask', 'C++']