◈ Python ◈ DP
Glossary:
grid[i][j]: The element at thei-th row andj-th column of the input grid, representing a positive integer value.
N_ROWS,N_COLS: The number of rows and
Glossary:

- $grid[i][j]$: The element at the $i$-th row and $j$-th column of the input grid, representing a positive integer value.
- $N\_ROWS$, $N\_COLS$: The number of rows and columns in the grid, respectively.
- $ix\_vals\_chosen$: A tuple representing the values chosen so far (Approach 1).
- $min\_next\_ix\_row$: The minimum allowed index for the next row to be chosen (Approach 1).
- $val2row2col$: A dictionary mapping each unique value in the grid to a dictionary of its row and column indices (Approach 2).
- $vals\_desc$: A list of unique values in the grid sorted in descending order (Approach 2).
- $ix\_rows\_chosen$: A tuple representing the indices of the rows chosen so far (Approach 2).
- $min\_next\_val$: The minimum allowed value for the next cell to be chosen (Approach 2).


Mathematical Intuition and Formulation:

The problem requires selecting a set of cells $S$ from the grid $grid$ to maximize the sum of their values, subject to the constraints:

1.  Uniqueness: All elements in $S$ are unique.
2.  Row-wise single selection: At most one cell can be selected from each row.

Approach 1:

This approach iterates over the rows, and at each row, decides whether to select a cell from that row or not. If a cell is selected, it must not have been selected previously. The state can be represented by a tuple $(i, V)$, where $i$ is the current row index and $V$ is the set of values chosen so far. The recurrence relation is:

$
dp(i, V) =
\begin{cases}
0, & \text{if } \space i = N\_ROWS \\
\max(\\
\quad dp(i + 1, V), \\
\quad \max_{j, grid[i][j] \notin V} \{grid[i][j] + dp(i + 1, V \cup \{grid[i][j]\})\}\\
), & \text{otherwise}
\end{cases}
$

The base case is when all rows have been processed ($i = N\_ROWS$), in which case the score is 0. Otherwise, the algorithm calculates the maximum score by either skipping the current row (`dp(i + 1, V)`) or choosing a value from the current row that has not been chosen previously ($grid[i][j] + dp(i + 1, V \cup \{grid[i][j]\})$).

The final answer is obtained by calling the `dp` function with the initial row index 0 and an empty set of chosen values:

$result = dp(0, \emptyset)$

Approach 2:

This approach iterates over the unique values in the grid. For each value, it decides whether to select a cell with that value or not. If a cell is selected, its row must not have been chosen previously. The state can be represented by a tuple $(R, v)$, where $R$ is the set of row indices chosen so far, and $v$ is the minimum allowed value for the next cell to be chosen. The recurrence relation is:

$
dp(R, v) =
\begin{cases}
0, & \text{if no cell with value } \ge v\space\text{ exists} \\
\max( \\
\quad dp(R, v + 1),\\
\quad  v + dp(R \cup \{i\}, v + 1)\\), & \text{otherwise, where } \space i \notin R ;\space grid[i][j] = v
\end{cases}
$

The final answer is $dp(\emptyset, -\infty)$.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
from collections import defaultdict as dd
import math
class Solution:
    def maxScore(self, *args) -> int:
        # return self.approach1(*args)
        return self.approach2(*args)
    """
    APPROACH - 2
    VERDICT - PASS
    Reference - https://leetcode.com/problems/select-cells-in-grid-with-maximum-score/solutions/5718001/bitmask-dp-mask-of-used-rows/?envType=problem-list-v2&envId=22pe56k2
    """
    def approach2(self, grid: List[List[int]]) -> int:
        N_ROWS, N_COLS = len(grid), len(grid[0])
        val2row2col = dd(lambda : dd(lambda : None))
        for ix_row in range(N_ROWS):
            for ix_col in range(N_COLS):
                val = grid[ix_row][ix_col]
                val2row2col[val][ix_row] = ix_col
        vals_desc = list(sorted(val2row2col.keys(),key=lambda x : -x))
        @lru_cache(maxsize=None)
        def dp(ix_rows_choosen=tuple(),min_next_val=None):
            next_val = None
            for val in vals_desc:
                if(min_next_val is None or val >= min_next_val):
                    next_val = val
            if(next_val is None):
                return None
            poss_arr = []
            # case 1 - skip val - next_val
            ix_rows_choosen1 = ix_rows_choosen
            min_next_val1 = next_val + 1
            poss_suffix1 = dp(ix_rows_choosen=ix_rows_choosen1,min_next_val=min_next_val1)
            poss_suffix = 0 + (0 if(poss_suffix1 is None)else poss_suffix1)
            poss_arr.append(poss_suffix)
            # case 2 - choose a row that has val - next_val
            for ix_row in val2row2col[next_val]:
                if(ix_row in ix_rows_choosen):
                    continue
                ix_rows_choosen1 = tuple(sorted(ix_rows_choosen+(ix_row,)))
                min_next_val1 = next_val + 1
                poss_suffix1 = dp(ix_rows_choosen=ix_rows_choosen1,min_next_val=min_next_val1)
                poss_suffix = next_val + (0 if(poss_suffix1 is None)else poss_suffix1)
                poss_arr.append(poss_suffix)
            return max(poss_arr , default=None)
        res = dp()
        return res
    """
    APPROACH - 1
    VERDICT : TLE
    """
    def approach1(self, grid: List[List[int]]) -> int:
        N_ROWS, N_COLS = len(grid), len(grid[0])
        @lru_cache(maxsize=None)
        def dp(ix_vals_choosen=tuple(),min_next_ix_row=None):
            poss_arr = []
            ix_row = 0 if(min_next_ix_row is None)else min_next_ix_row
            if(ix_row>=N_ROWS):
                return None
            # case - 1 - skip row - ix_row
            ix_vals_choosen1 = ix_vals_choosen
            min_next_ix_row1 = ix_row +1
            poss_suffix = dp(ix_vals_choosen=ix_vals_choosen1,min_next_ix_row=min_next_ix_row1)
            poss_suffix1 = (0 if(poss_suffix is None)else poss_suffix)
            poss_arr.append(poss_suffix1)

            # case - 2 - choose a value from row - ix_row
            for val in grid[ix_row]:
                if(val in ix_vals_choosen):
                    continue
                ix_vals_choosen1 = tuple(sorted(ix_vals_choosen+(val,)))
                min_next_ix_row1 = ix_row +1
                poss_suffix = dp(ix_vals_choosen=ix_vals_choosen1,min_next_ix_row=min_next_ix_row1)
                poss_suffix1 = val + (0 if(poss_suffix is None)else poss_suffix)
                poss_arr.append(poss_suffix1)
            return max(poss_arr , default=None)
        res = dp()
        return res
```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python3']