Skip to content

3276. Select Cells in Grid With Maximum Score 👍

  • Time: $O(100 \cdot m^2)$
  • Space: $O(100 \cdot m)$
 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
class Solution {
 public:
  int maxScore(vector<vector<int>>& grid) {
    unordered_map<int, unordered_set<int>> numToIndices;
    for (int index = 0; index < grid.size(); ++index)
      for (const int num : grid[index])
        numToIndices[num].insert(index);
    vector<vector<int>> mem(numToIndices.size(), vector<int>(1 << grid.size()));
    return maxScore({numToIndices.begin(), numToIndices.end()}, 0, 0, mem);
  }

 private:
  // Returns the maximum score by selecting numbers from numToIndices[i..],
  // where `mask` is the bitmask of the used row indices.
  int maxScore(const vector<pair<int, unordered_set<int>>>& numToIndices, int i,
               int mask, vector<vector<int>>& mem) {
    if (i == numToIndices.size())
      return 0;
    if (mem[i][mask] != 0)
      return mem[i][mask];
    // Skip numToIndices[i].first.
    int res = maxScore(numToIndices, i + 1, mask, mem);
    for (const int index : numToIndices[i].second)
      if ((mask >> index & 1) == 0)
        // Take numToIndices[i].first.
        res =
            max(res, numToIndices[i].first +
                         maxScore(numToIndices, i + 1, mask | 1 << index, mem));
    return mem[i][mask] = 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
class Solution {
  public int maxScore(List<List<Integer>> grid) {
    Map<Integer, Set<Integer>> numToIndices = new HashMap<>();
    for (int index = 0; index < grid.size(); ++index)
      for (final int num : grid.get(index)) {
        numToIndices.putIfAbsent(num, new HashSet<>());
        numToIndices.get(num).add(index);
      }
    int[][] mem = new int[numToIndices.size()][1 << grid.size()];
    return maxScore(new ArrayList<>(numToIndices.entrySet()), 0, 0, mem);
  }

  // Returns the maximum score by selecting numbers from numToIndices[i..],
  // where `mask` is the bitmask of the used row indices.
  private int maxScore(List<Map.Entry<Integer, Set<Integer>>> numToIndices, int i, int mask,
                       int[][] mem) {
    if (i == numToIndices.size())
      return 0;
    if (mem[i][mask] != 0)
      return mem[i][mask];
    // Skip numToIndices[i].getKey().
    int res = maxScore(numToIndices, i + 1, mask, mem);
    for (int index : numToIndices.get(i).getValue())
      if ((mask >> index & 1) == 0)
        // Take numToIndices[i].getKey().
        res = Math.max(res, numToIndices.get(i).getKey() +
                                maxScore(numToIndices, i + 1, mask | (1 << index), mem));
    return mem[i][mask] = 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
class Solution:
  def maxScore(self, grid: list[list[int]]) -> int:
    numToIndices = collections.defaultdict(set)
    for index, row in enumerate(grid):
      for num in row:
        numToIndices[num].add(index)
    numToIndices = list(numToIndices.items())

    @functools.lru_cache(None)
    def dp(i: int, mask: int) -> int:
      """
      Returns the maximum score by selecting numbers from numToIndices[i..],
      where `mask` is the bitmask of the used row indices.
      """
      if i == len(numToIndices):
        return 0
      # Skip numToIndices[i][0].
      res = dp(i + 1, mask)
      for index in numToIndices[i][1]:
        if (mask >> index & 1) == 0:
          # Take numToIndices[i][0].
          res = max(res, numToIndices[i][0] + dp(i + 1, mask | 1 << index))
      return res

    return dp(0, 0)