C++ greedy + bitmask dp solution
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition here is that we can traverse through the rows and keep a bitmask of the n
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition here is that we can traverse through the rows and keep a bitmask of the numbers taken. However the maximum value of the number can be 100 and (2^100) bits will be required to represent them.\nHence a better approach is to keep track of a bitmask of the rows taken.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWhen considering a row it always is better to take the maximum possible value. Hence we start from the maximum possible value in the grid and map it to the row it is present in. Now inside the main recursive function when we consider to take this current maximum element it can be taken from any of the rows it is present in(The row should currently be avaliable too).\nAlso at each step it is always an option to not consider the current maximum and decrease it.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n * max(grid))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO((2 ^ n)*(max(grid)))\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int dp[101][(1 << 10) + 1];\n    vector<int> row_mappings[101];\n    int solve(int cur_max, int row_mask){\n        if(cur_max == 0){\n            return 0; // all elements explored\n        }\n        if(dp[cur_max][row_mask] != -1){\n            return dp[cur_max][row_mask];\n        }\n        int ans = solve(cur_max - 1, row_mask); // maybe not taking cur_max is the best way\n        for(int i : row_mappings[cur_max]){\n            if(row_mask & (1 << i)){\n                continue; // if the row is already taken do not consider\n            }\n            int new_mask = row_mask | (1 << i);\n            ans = max(ans, cur_max + solve(cur_max - 1, new_mask));\n        }\n        dp[cur_max][row_mask] = ans;\n        return ans;\n    }\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        int mx = -1;\n        for(int i = 0; i < n; i++){\n            for(int j = 0; j < m; j++){\n                row_mappings[grid[i][j]].push_back(i); // map the elements to the rows thay are present in\n                mx = max(mx, grid[i][j]);\n            }\n        }\n        for(int i = 1; i <= mx; i++){\n            for(int j = 0; j <= (1 << n); j++){\n                dp[i][j] = -1;\n            }\n        }\n        return solve(mx, 0); // start from the maximum in the grid\n    }\n};\n```
['Dynamic Programming', 'Greedy', 'Bitmask', 'C++']