# LC 3276. Select Cells in Grid With Maximum Score

### [Problem link](https://leetcode.com/problems/select-cells-in-grid-with-maximum-score/)

###### tags: `leedcode` `hard` `c++` `DP`

You are given a 2D matrix <code>grid</code> consisting of positive integers.

You have to select one or more cells from the matrix such that the following conditions are satisfied:

- No two selected cells are in the **same** row of the matrix.
- The values in the set of selected cells are **unique** .

Your score will be the **sum** of the values of the selected cells.

Return the **maximum** score you can achieve.

**Example 1:**

<div class="example-block">
Input: <span class="example-io">grid = [[1,2,3],[4,3,2],[1,1,1]]

Output: <span class="example-io">8

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/07/29/grid1drawio.png" />

We can select the cells with values 1, 3, and 4 that are colored above.

**Example 2:**

<div class="example-block">
Input: <span class="example-io">grid = [[8,7,6],[8,3,2]]

Output: <span class="example-io">15

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/07/29/grid8_8drawio.png" style="width: 170px; height: 114px;" />

We can select the cells with values 7 and 8 that are colored above.

**Constraints:**

- <code>1 <= grid.length, grid[i].length <= 10</code>
- <code>1 <= grid[i][j] <= 100</code>

## Solution 1 - DP
#### C++

class Solution {
public:
    int dfs(vector<vector<int>>& memo, unordered_map<int, unordered_set<int>>& pos, int i, int j) {
        if (i == 0) {
            return 0;
        }
        int& res = memo[i][j];
        if (res != -1) {
            return res;
        }
        res = dfs(memo, pos, i - 1, j);
        for (int k: pos[i]) {
            if (((j >> k) & 1) == 0) {
                res = max(res, dfs(memo, pos, i - 1, j | (1 << k)) + i);
            }
        }
        return res;
    }

    int maxScore(vector<vector<int>>& grid) {
        int maxVal = 0;
        unordered_map<int, unordered_set<int>> pos;
        for (int row = 0; row < grid.size(); row++) {
            for (int col = 0; col < grid[0].size(); col++) {
                pos[grid[row][col]].insert(row);
                maxVal = max(maxVal, grid[row][col]);
            }
        }

        vector<vector<int>> memo(maxVal + 1, vector<int>(1 << 12, -1));
        // memo[i][j] => i: [1: i]中選擇數字, j: 已選的行數
        return dfs(memo, pos, maxVal, 0);
    }
};

>### Complexity
>m = grid.row
>n = grid.col
>k = number of distinct elements in the grid
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(2^m) | O(k2^m) |

## Note
TC: O(mn + 2^m) = O(2^m)
SC: O(mn + k2^m) = O(k2^m)

[reference](https://leetcode.cn/problems/select-cells-in-grid-with-maximum-score/solutions/2899994/zhi-yu-zhuang-ya-dppythonjavacgo-by-endl-x27y/)