DP with a little bit greedy
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is essentially about selecting cells from the matrix with the constraints t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is essentially about selecting cells from the matrix with the constraints that no two selected cells are from the same row and that all selected values are unique. To maximize the sum of selected values, we can use dynamic programming combined with bitmasking.\n\nThe bitmask will help us track which rows have been selected so far, while dynamic programming will help us find the optimal solution step by step.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Bitmask Representation:\n\n    * We represent the selection of rows using bitmasking. If we have $m$ rows, a bitmask of length $m$ can represent any subset of these rows. For example, if we have $3$ rows, the bitmask `011` would indicate that rows $2$ and $3$ have been selected.\n    \n2. Mapping Numbers to Rows:\n\n    * We create a dictionary `dic` where each key is a number in the grid, and the corresponding value is a bitmask representing the rows where this number appears. This helps in checking the availability of a number across different rows quickly.\n    \n3. Dynamic Programming:\n\n    * We use dynamic programming (`dp`) to store the maximum sum possible for each bitmask representing a set of selected rows.\n\n    * We initialize the `dp` table with a bitmask representing all rows unselected (i.e., `(1 << m) - 1` where m is the number of rows) having a score of $0$.\n    * Then, iterating over the numbers in descending order, we update our `dp` table by considering whether to include the current number based on whether it fits the constraints.\n    * **Greedy-like selection:** Notice that in cases where the current number fits, it must be included to update the bitmask (i.e., the current selection of cells must be expanded by a cell with the current number) to maximize the score; otherwise, we just keep our selection in this turn. \n    \n4. Final Result:\n\n    * The answer is the maximum value in the `dp` table after processing all the numbers.\n\n# Complexity\n* Time complexity:\n    * Constructing the dictionary `dic` takes $\uD835\uDC42(\uD835\uDC5A \\times \uD835\uDC5B)$, where $m$ is the number of rows and $n$ is the number of columns.\n    * Sorting the keys in `dic` takes $\uD835\uDC42(\uD835\uDC41\\log \uD835\uDC41)$, where $N$ is the number of unique elements in the grid.\n    * The main DP step iterates over the sorted keys and for each key checks all possible masks, resulting in a complexity of $\uD835\uDC42(\uD835\uDC41\\times 2^\uD835\uDC5A\\times \uD835\uDC5A)$. Thus, the overall time complexity is $\uD835\uDC42(\uD835\uDC41\\times 2^m \\times \uD835\uDC5A)$, which is efficient when $m$ is small.\n\n* Space Complexity:\n\nThe space complexity is dominated by the `dp` table, which has a size of $\uD835\uDC42(2^\uD835\uDC5A)$. Additionally, `dic` takes $\uD835\uDC42(\uD835\uDC41)$ space.\n\n# Code\n```python3 []\n\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        # dic will map each number to the bitmask representing the rows it appears in\n        dic = defaultdict(int)\n        \n        for i in range(m):\n            l = 1 << i  # Create a bitmask where only the ith row is marked\n            for num in grid[i]:\n                dic[num] |= l  # Mark the rows in which this number appears\n\n        # dp stores the maximum score possible for each bitmask of rows\n        dp = {(1 << m) - 1: 0}  # Start with all rows unselected, score 0\n        \n        # Iterate over numbers in descending order of their values\n        for num in sorted(dic.keys(), reverse=True):\n            new = {}\n            for mask in dp:\n                temp = dic[num] & mask  # temp stores the available rows for current number\n                \n                if not temp:\n                    # If the current number can\'t be placed in any available row, just carry forward the current score\n                    if mask not in new:\n                        new[mask] = dp[mask]\n                    else:\n                        new[mask] = max(new[mask], dp[mask])\n                else:\n                    # If the current number can be placed in some available row\n                    for i in range(m):\n                        l = 1 << i\n                        if temp & l:  # Check if row i is available\n                            t = mask ^ l  # Create a new mask with row i selected\n                            if t in new:\n                                new[t] = max(new[t], dp[mask] + num)\n                            else:\n                                new[t] = dp[mask] + num\n            dp = new  # Update dp with new values\n        \n        # The result is the maximum value in the dp dictionary\n        return max(dp.values())\n\n```
['Python3']