3276. Select Cells in Grid With Maximum Score

Posted on Edited on In

3276. Select Cells in Grid With Maximum Score

Description

You are given a 2D matrix grid 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:

1
2
3
Input: grid = [[1,2,3],[4,3,2],[1,1,1]]

Output: 8

Explanation:

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

Example 2:

1
2
3
Input: grid = [[8,7,6],[8,3,2]]

Output: 15

Explanation:

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

Constraints:

  • 1 <= grid.length, grid[i].length <= 10
  • 1 <= grid[i][j] <= 100

Hints/Notes

  • 2024/09/01
  • state compression dp
  • bit manipulation
  • 0x3F’s solution(checked, didn’t check iteration since recursion works better)
  • Weekly Contest 413

Solution

Language: C++

Better approach with bit manipulation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    // the meaning of dp[i][j]:
    //  with maxVal of i, and we can choose from the rows
    //  not marked by j, what's the maximum value we can get
    vector<vector<int>> dp;
    vector<int> nums;
    map<int, int> valToRow;

    int maxScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x = grid[i][j];
                valToRow[x] |= 1 << i;
            }
        }
        for (auto&[num, _] : valToRow) {
            nums.push_back(num);
        }
        ranges::sort(nums);
        int size = nums.size();
        dp.resize(size, vector<int>(2 << m, -1));
        int res = dfs(size - 1, 0);
        return res;
    }

    int dfs(int idx, int k) {
        if (idx < 0) {
            return 0;
        }
        if (dp[idx][k] != -1) {
            return dp[idx][k];
        }
        int res = 0, x = nums[idx];
        for (int i = valToRow[x], bit; i; i ^= bit) {
            bit = i & -i;
            if (!(k & bit)) {
                res = max(res, dfs(idx - 1, k | bit) + x);
            }
        }
        if (!res) {
            res = dfs(idx - 1, k);
        }
        dp[idx][k] = res;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    // the meaning of dp[i][j]:
    //  with maxVal of i, and we can choose from the rows
    //  not marked by j, what's the maximum value we can get
    vector<vector<int>> dp;
    vector<unordered_set<int>> valToRow;

    int maxScore(vector<vector<int>>& grid) {
        int maxVal = 0, m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxVal = max(maxVal, grid[i][j]);
            }
        }
        dp.resize(maxVal + 1, vector<int>(2 << m, -1));
        // valToRow is to avoid duplication and simplify the iteration
        valToRow.resize(maxVal + 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                valToRow[grid[i][j]].insert(i);
            }
        }
        int res = dfs(maxVal, 0);
        return res;
    }

    int dfs(int maxVal, int k) {
        if (maxVal <= 0) {
            return 0;
        }
        if (dp[maxVal][k] != -1) {
            return dp[maxVal][k];
        }
        int res = dfs(maxVal - 1, k);
        for (int row : valToRow[maxVal]) {
            if (!(k >> row & 1)) {
                res = max(res, dfs(maxVal - 1, k | 1 << row) + maxVal);
            }
        }
        dp[maxVal][k] = res;
        return res;
    }
};