Select Cells in Grid With Maximum Score

Problem Description

Ah, the classic dilemma of choosing the best cells in a grid to maximize your score! It’s like trying to pick the best slice of pizza at a party where everyone is eyeing the last piece. You want to grab the tastiest slice (or in this case, the highest score) without stepping on anyone’s toes (or in this case, without selecting from the same row).

In this problem, you are given a grid filled with numbers, and your task is to select numbers such that no two numbers come from the same row. The catch? You want to maximize the total score of the selected numbers. It’s like a game of musical chairs, but instead of chairs, you have numbers, and instead of music, you have a ticking clock reminding you that your score is on the line!

Code Solution

class Solution {
 public:
  int maxScore(vector>& grid) {
    unordered_map> numToIndices;
    for (int index = 0; index < grid.size(); ++index)
      for (const int num : grid[index])
        numToIndices[num].insert(index);
    vector> mem(numToIndices.size(), vector(1 << grid.size()));
    return maxScore({numToIndices.begin(), numToIndices.end()}, 0, 0, mem);
  }

 private:
  int maxScore(const vector>>& numToIndices, int i,
               int mask, vector>& mem) {
    if (i == numToIndices.size())
      return 0;
    if (mem[i][mask] != 0)
      return mem[i][mask];
    int res = maxScore(numToIndices, i + 1, mask, mem);
    for (const int index : numToIndices[i].second)
      if ((mask >> index & 1) == 0)
        res = max(res, numToIndices[i].first +
                         maxScore(numToIndices, i + 1, mask | 1 << index, mem));
    return mem[i][mask] = res;
  }
};
    

Approach Explanation

The approach taken in this solution is a classic example of dynamic programming combined with bitmasking. The idea is to use a recursive function that explores all possible selections of numbers while keeping track of which rows have already been used (using a bitmask).

1. Mapping Numbers to Indices: First, we create a mapping of numbers to their respective row indices. This helps us quickly find which rows we can select from for each number.
2. Recursive Exploration: The recursive function maxScore explores two options for each number: either skip it or select it (if it hasn’t been selected from its row yet).
3. Memoization: To avoid recalculating results for the same state, we store results in a memoization table.

Time and Space Complexity

Time Complexity: O(N * 2^M), where N is the number of unique numbers and M is the number of rows. This is due to the recursive exploration of all combinations of row selections.

Space Complexity: O(N * 2^M) for the memoization table.

Real-World Example

Imagine you’re at a buffet with a variety of dishes, and you want to maximize your meal without repeating any dish from the same category (like appetizers, main courses, and desserts). You have to make strategic choices to ensure you get the most delicious combination without doubling up on any category. This mirrors the problem of selecting cells in a grid to maximize your score while adhering to the row selection constraint.

Similar Problems