Simple Explanation + intuition, w/ Handwritten color-coded drawings and notes.
Intuition\n Describe your first thoughts on how to solve this problem. \n\nFULL PDF OF ALL HANDWRITTEN NOTES CAN BE FOUND HERE: https://drive.google.com/file/d/
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n**FULL PDF OF ALL HANDWRITTEN NOTES CAN BE FOUND HERE:** https://drive.google.com/file/d/1Sw1p2ScKndGBbUixW6T4SScUPiWBNj99/view?usp=sharing\n\n- Initially, upon seeing this problem, it\'s immediately obvious that a decision tree can be made.\n- We have the constraints of A.) only picking one value from each row, and B.) only selecting unique values. So, rows must be unique as well as values.\n- So, if we construct a backtracking solution, we could keep track of what row we\'re on, as well as a list of elements already selected, and iterate through, generating a recursion path for each value that is not already selected in each row. This could work, but it results in TLE (Time Limit Exceeded).\n- We can make this faster. We know that we have two constraints, "one value from each row", and, "each value must be unique," so, there is a clue here that we could use 2D Dynamic Programming.\n- The hard part is guessing what keys to use for the 2D Dynamic Programming. That\'s where I failed on this problem when I did it as part of Weekly Competition 413.\n- So, the key of what rows have been used is easier. The grid is a maximum of 10x10 elements, which means there is a maximum of 10 rows. We can use a bitmask to keep track of what rows have been used in an efficient manner, with the n-th bit corresponding with the n-th row. If you\'re using a typed language, anything 2-bytes (16 bits) or larger should work.\n- The other key, elements we already selected, was a bit less intuitive for me. A set cannot be used as a key, so a set of all of the elements we have selected thus far won\'t work. We could try using a sorted tuple, which might work, but that could create some additional overhead and didn\'t seem very clean to me. This is probably a solution I would have come to though if i spent more time on it.\n- So, what do we do? Well, we can actually turn the grid into a list of `(value, row, col)` tuples, and sort it. When sorting it, the first element `value` will be the most significant element used in the sorting, so we\'re essentially creating a sorted list of values and still maintaining their row/column information. This allows us to simply cache an index `i` in DP, and we know that at `i`, we can just go to the next unique value in the list and we\'ll never see the same value again, since it\'s sorted.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Building off of the intuition, we first construct a list `values` which is a sorted list of tuples `(grid[i][j], i, j)`.\n- Then, we initialize a hashmap for DP, where the keys will be `(index: int, row_bitmask: int)` and the values will be `points: int`.\n- A recursive top-down memoization approach is used. The method needs to have access to the values array, the DP hashmap, and will have the parameters for the current index `i` and the rows that have been selected so far `rows` represented as a bitmask.\n![image.png](https://assets.leetcode.com/users/images/4d97f593-748a-4236-95a5-4e1a8b336ac6_1725260758.2596042.png)\n\n\n- `i` will be the index of the current value in `values` that we\'re at. We will have an exit condition that will result in the method exiting when `i >= len(values)`, since there are no more points to be gained at that stage.\n- If the current value\'s row has already been seen, then we simply move on to the next value.\n- Otherwise, we have two possible paths:\n    1. We can try selecting the current value and moving to the next unique value in the list for the next recursive step\n    2. we can not select the current value and simply move on to the next value\n    3. We return the maximum of these two paths as the result.\n\n![image.png](https://assets.leetcode.com/users/images/7f36e6f4-2a47-4a15-a475-f8ee6f88b031_1725260827.9910643.png)\n\n\n# Complexity\nNot 100% sure on these, but thinking through this, the worst case scenario is that we keep hitting the else block for each value, which results in two paths, and if the number of values in the grid is `N`, then the time complexity here would be:\n\n- Time complexity: $O(2^N)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: $O(2^N)$ \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nI\'m pretty sure this worst case scenario would also only happen if we had just one value per row. Anyone who has a better or more rigorous answer for the time complexity, feel free to comment and I can edit this answer and credit you.\n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        # generate a sorted list of (value, row, col) in the grid.\n        # this sorting will happen in lexographical order, just like\n        # ordering something alphabetically. So, `value` will be the\n        # most significant element, but if `value[i] == value[j], i != j`,\n        # then the next most significant element is what row they\n        # are in. \n        values = sorted([(grid[i][j], i, j) for i in range(len(grid)) for j in range(len(grid[0]))])\n\n        dp = {}\n        def solve(i, rows):\n            # If we\'ve tried all of the values, just exit.\n            # no more points to be gained.\n            if i >= len(values):\n                return 0\n\n            # if we\'ve already solved the path at this point,\n            # from this index with this combination of rows already\n            # selected, then simply return that cached result\n            if (i, rows) in dp:\n                return dp[(i, rows)]\n\n            # will store the result\n            res = 0\n            # Each value in values is a tuple of (value, row, col). So,\n            # here we get the row from the value at the current index\n            # for this recusion step.\n            cur_row = values[i][1]\n\n            # here, we check if we have already selected a value\n            # from the current row. If so, we\'ll just move on to the\n            # next value in the list, skipping over this one, since\n            # this one can\'t be selected.\n            if (rows & (1 << cur_row)):\n                res = solve(i+1, rows)\n            # If we haven\'t already selected a value from this row,\n            # then we have the option to either select one or not select one.\n            # so there are two potential paths in the else block.\n            else:\n                # get the index of the next unique value.\n                j = i\n                while (j < len(values)) and (values[i][0] == values[j][0]):\n                    j += 1\n                \n                # here, we select this value and continue at the index\n                # of the next unique value (since values is sorted, and\n                # we can\'t select two of the same value, this will be\n                # the next smallest value). We use the OR operator to\n                # set the bit corresponding with the row of this element\n                # we\'re selecting in the `rows` bitmask.\n                path1 = values[i][0] + solve(j, rows | (1 << cur_row))\n\n                # Otherwise, we can choose not to select this value and\n                # just move on to the next value in the values list.\n                path2 = solve(i+1, rows)\n\n                # the result will be the maximum of the two paths,\n                # since we want to maximize our score:\n                res = max(path1, path2)\n            \n            # cache and return the result\n            dp[(i, rows)] = res\n            return res\n\n        # thanks to https://leetcode.com/u/virujthakur01/ for inspiring\n        # this solution. I adapted the python code here from his C++ solution,\n        # and used his solution to understand the problem and gain\n        # the necessary insight and intuition to solve it.\n        return solve(0,0)\n```\n\n# Credit\n- thanks to https://leetcode.com/u/virujthakur01/ for inspiring this solution. I adapted the python code here from his [C++ solution](https://leetcode.com/problems/select-cells-in-grid-with-maximum-score/solutions/5718075/focus-on-uniqueness-in-values-first-then-uniqueness-in-rows-full-explanation/), and used his solution to understand the problem and gain the necessary insight and intuition to solve it.
['Python3']