bit-mask DP by limiting and enumerating the current largest element
Intuition\n1. Bit-mask DP takes care of the first condition: "no two selected cells are in the same row of the matrix."\n2. To satisfy the second requirement: "
# Intuition\n1. Bit-mask DP takes care of the first condition: "no two selected cells are in the same row of the matrix."\n2. To satisfy the second requirement: "the values in the set of selected cells are unique," we can require the selected value list is strictly decreasing. One way to achieve in DP is to add a new dimension `M` to cap the largest element we can select. \n\n# Approach\nLet `f[mask][M]` denote the largest sum we can achieve given a set of rows (denoted by bit-mask `mask`), where all the elements we choose are no greater than `M` and we always obey the two rules.\n\nThe base case is `f[0][M] = 0`.\nTo make the DP work, one idea is to enumerate the largest element from the current setup (say it\'s from `grid[i][j]`), where (i) `i` belongs to `mask` and `grid[i][j] <= M`. Then, we can recur on `f[mask - (1 << i)][grid[i][j] - 1]` since (i) row i has already been chosen and (ii) all the remaining elements now must be strictly less than `grid[i][j]`.\n\n# Complexity\n- Time complexity: $O(CRM2^R)$, where $R$ is the number of rows, $C$ is the number of columns, and $M$ is the largest element of the matrix ($M \\le 100$ for this problem). I believe the factor $R$ can be removed by carefully enumerating exactly those bits each `mask` contains, but the current complexity is already good enough to pass all the test cases while keeping the code simple.\n\n- Space complexity: $O(CM2^R)$\n\n# Code\n```python3\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        R = len(grid)\n        C = len(grid[0])\n\n        @cache\n        def f(mask, M):\n            if mask == 0:\n                return 0\n            ans = 0\n            for i in range(R):\n                if mask & (1 << i):\n                    for j in range(C):\n                        if grid[i][j] <= M:\n                            ans = max(ans, f(mask - (1 << i), grid[i][j] - 1) + grid[i][j])\n            return ans\n\n        ans = f((1 << R) - 1, 100)\n        return ans\n```\n\n# Column Optimization - Binary Search\n\nNote that `f[mask][m] <= f[mask][M]` for any `m <= M`. Therefore, we only need to find the largest `grid[i][j] <= M` among all `j`s, which can be done quickly via binary search if we pre-sort all `grid[i]`s. This improves the runtime to $O(RM2^R\\log C + RC \\log C)$.\nIn practice, we approximately see runtime reduces to 1/5 of the previous version.\n\n\n```python3\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        R = len(grid)\n        for i in range(R):\n            grid[i].sort()\n\n        @cache\n        def f(mask, M):\n            if mask == 0:\n                return 0\n            ans = 0\n            for i in range(R):\n                if mask & (1 << i):\n                    j = bisect.bisect_right(grid[i], M) - 1\n                    if j >= 0:\n                        ans = max(ans, f(mask - (1 << i), grid[i][j] - 1) + grid[i][j])\n            return ans\n\n        ans = f((1 << R) - 1, 100)\n        return ans\n\n```\n\n# Row Optimization -- Greedy\nAccording to @porker2008\'s great comment, we can always pick the rows with the largest elements not greater than M instead of checking all the rows. This turns out to be a very strong pruning techinical in practice.\n```python3\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        R = len(grid)\n        for i in range(R):\n            grid[i].sort()\n\n        @cache\n        def f(mask, M):\n            if mask == 0:\n                return 0\n            cand = []\n            for i in range(R):\n                if mask & (1 << i):\n                    j = bisect.bisect_right(grid[i], M) - 1\n                    if j >= 0:\n                        cand.append((grid[i][j], i))\n            if not cand:\n                return 0\n            max_v = max(cand)[0]\n            return max(f(mask - (1 << i), m - 1) + m for m, i in cand if m == max_v)\n\n        return f((1 << R) - 1, 100)\n```\n\n\n\n
['Python3']