[Python3] DP bitmask 15 lines
\n# Intuition\n> The condition 1 <= grid.length, grid[i].length <= 10 suggests that the problem\'s constraints are small, making bitmasks a suitable choice for 
\n# Intuition\n> The condition `1 <= grid.length, grid[i].length <= 10` suggests that the problem\'s constraints are small, making bitmasks a suitable choice for tracking which rows have been used.\n\nThe goal is to maximize the score by selecting values from the grid while ensuring that each row is used only once. To do this, you can leverage dynamic programming to explore all possible combinations of selecting values and track the maximum score for each combination.\n\n# Approach\n1. **Mapping Values to Rows:** Create a mapping from each value to the rows in which it appears.\n2. **Dynamic Programming (DP) Setup:** Use a DP dictionary where the keys are bitmasks representing which rows have been used, and the values are the maximum score achievable with those rows.\n3. **Iterate Over Values:** For each unique value, update the DP dictionary by considering all possible bitmasks and determining the maximum score achievable by adding the current value if the rows it occupies are not already used.\n4. **Return Result:** The maximum value in the DP dictionary after processing all values will be the answer.\n\n# Complexity\n- **Time complexity:** $O(2^m \\cdot m \\cdot \\log k)=O(2^{10}\\cdot 10 \\cdot \\log 100)=O(20480)$ where $m$ is the number of rows and $k$ is the number of unique values. The factor $2^m$ comes from iterating over all possible bitmasks, and $m \\cdot \\log k$ accounts for the operations involving updating the DP table and processing values.\n- **Space complexity:** $O(2^m)=O(2^{10})=O(1024)$ for the DP dictionary storing scores for each bitmask combination.\n\n# Code\n```python3\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        # Map each value to the rows it appears in\n        value_to_rows = defaultdict(set)\n        for r, row in enumerate(grid):\n            for val in row:\n                value_to_rows[val].add(r)\n        \n        # Initialize DP table where key is a bitmask of used rows and value is the maximum score\n        dp = defaultdict(int, {0: 0})\n\n        \n        # Process each unique value in descending order\n        for value in sorted(value_to_rows)[::-1]:\n            for bitmask in list(dp):\n                score = dp[bitmask]\n                # Update DP table by including the current value\n                for r in value_to_rows[value]:\n                    if not (bitmask & (1 << r)):\n                        dp[bitmask | (1 << r)] = max(dp[bitmask | (1 << r)], score + value)\n        \n        # Return the maximum score from the DP table\n        return max(dp.values())\n```
['Dynamic Programming', 'Greedy', 'Python3']