🔢 Maximum Score Selection in Grid with Unique Value Constraints 🧮
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem involves selecting cells from a grid in such a way that the sum of selected
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem involves selecting cells from a grid in such a way that the sum of selected cell values is maximized. The selection rules are:\n- No two selected cells can be from the same row.\n- The values in the selected cells must be unique.\n\nThis problem can be approached by dynamically keeping track of possible selections using a bitmask to represent selected rows. By iterating over all possible values, starting from the largest, we can ensure that the maximum possible score is obtained.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Preprocessing:\n\n    - First, create a dictionary (value_positions) that maps each unique value in the grid to the list of its positions (row, column) in the grid.\n    - Sort the unique values in descending order, so that we can process the largest values first.\n2. Dynamic Programming with Bitmask:\n    - Use a bitmask to represent the set of rows that have been selected. The dp array is used where dp[mask] holds the maximum score for a given mask configuration.\n    - For each value, iterate through its positions in the grid and update the dp array by considering adding this value to each possible configuration of the selected rows.\n    - The new_dp array is used to store the updated scores after considering the current value. This ensures that each value is only added once per row configuration.\n3. Result:\n    - After processing all values, the maximum score can be found in the dp array.\n\n# Complexity\n- Time complexity: O(V * 2^m) where V is the number of unique values in the grid, and m is the number of rows. For each value, we potentially update 2^m states.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(2^m) due to the dp array, where m is the number of rows.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n\n        m, n = len(grid), len(grid[0])\n        \n        value_positions = defaultdict(list)\n        for i in range(m):\n            for j in range(n):\n                value_positions[grid[i][j]].append((i, j))\n        \n        sorted_values = sorted(set(v for row in grid for v in row), reverse=True)\n        \n        dp = [0] * (1 << m)\n        \n        \n        for value in sorted_values:\n            new_dp = dp.copy()\n            for positions in value_positions[value]:\n                i, j = positions\n                for mask in range(1 << m):\n                    if mask & (1 << i) == 0:\n                        new_mask = mask | (1 << i)\n                        new_dp[new_mask] = max(new_dp[new_mask], dp[mask] + value)\n            dp = new_dp\n        \n        return max(dp)\n\n        \n```
['Hash Table', 'Dynamic Programming', 'Python3']