Select Cells in Grid With Maximum Score

• Define a recursive function backtrack(rowIndex, currentScore, usedValues, grid).
• The base case for the recursion is when rowIndex equals the total number of rows. At this point, update the global maximum score with currentScore.
• In the recursive step, for the current rowIndex, explore two main branches:
  1. Skip the row: Make a recursive call for the next row: backtrack(rowIndex + 1, currentScore, usedValues, grid).
  2. Select a cell: Iterate through each column col of the current row.
     • Let value = grid[rowIndex][col].
     • If value is not present in the usedValues set, it's a valid choice.
     • Add value to usedValues.
     • Make a recursive call for the next row with the updated score and used values: backtrack(rowIndex + 1, currentScore + value, usedValues, grid).
     • After the recursive call returns, remove value from usedValues to backtrack and explore other possibilities.
• The initial call to start the process is backtrack(0, 0, new HashSet<>(), grid).

The brute-force backtracking approach systematically explores every valid combination of cells. The core of this method is a recursive function that traverses through the rows of the grid. For each row, it considers two possibilities: either skipping the row entirely or selecting one cell from it. If a cell is selected, its value must not have been chosen from any of the previous rows. This process builds a search tree where each path from the root to a leaf represents a valid selection. The score of each path is calculated, and the maximum score found across all paths is the answer.

1class Solution {2    int maxScore = 0;3 4    public int selectCells(int[][] grid) {5        backtrack(0, 0, new HashSet<>(), grid);6        return maxScore;7    }8 9    private void backtrack(int rowIndex, int currentScore, Set<Integer> usedValues, int[][] grid) {10        if (rowIndex == grid.length) {11            maxScore = Math.max(maxScore, currentScore);12            return;13        }14 15        // Option 1: Skip the current row16        backtrack(rowIndex + 1, currentScore, usedValues, grid);17 18        // Option 2: Pick one cell from the current row19        for (int col = 0; col < grid[rowIndex].length; col++) {20            int value = grid[rowIndex][col];21            if (!usedValues.contains(value)) {22                usedValues.add(value);23                backtrack(rowIndex + 1, currentScore + value, usedValues, grid);24                usedValues.remove(value); // backtrack25            }26        }27    }28}

• Preprocessing:
  • Create a map locations to store the row indices for each unique value in the grid. For example, locations.get(v) will return a list of rows containing the value v.
  • Extract all unique values from the grid into a list, uniqueValues. Sort this list in descending order. This helps in finding larger scores earlier, though it's not strictly necessary for correctness.
• DP with Memoization:
  • Define a recursive function solve(k, usedRowsMask) which returns the maximum score obtainable from considering values uniqueValues[k:], given that the rows indicated by usedRowsMask are already occupied.
  • k is the index of the current value being considered from the uniqueValues list.
  • usedRowsMask is a bitmask where the i-th bit is 1 if a cell has already been selected from row i.
  • Use a 2D array memo[k][usedRowsMask] to store and retrieve results of subproblems.
• Base Case: If k equals the number of unique values, we have considered all values, so we return 0.
• Recursive Step: For the current value val = uniqueValues[k], calculate the maximum score by considering two choices:
  1. Skip val: The score is solve(k + 1, usedRowsMask).
  2. Select val: Iterate through all rows r where val is located (from the locations map). If row r is not yet used (i.e., the r-th bit in usedRowsMask is 0), calculate the score as val + solve(k + 1, usedRowsMask | (1 << r)).
• The function returns the maximum score found among all these choices, storing it in the memoization table before returning.
• The initial call is solve(0, 0).

This approach reframes the problem to make it suitable for dynamic programming. The state of our DP is defined by (k, usedRowsMask), where k is the index of the unique value we are currently considering, and usedRowsMask is a bitmask representing the rows that are already occupied. By iterating through the unique values and for each, deciding whether to use it (and in which available row) or skip it, we can build the solution optimally. Memoization is crucial to store the results of subproblems (k, usedRowsMask) to avoid re-calculating them.

1class Solution {2    private List<Integer> uniqueValues;3    private Map<Integer, List<Integer>> locations;4    private int[][] memo;5    private int numRows;6 7    public int selectCells(int[][] grid) {8        numRows = grid.length;9        locations = new HashMap<>();10        Set<Integer> valueSet = new HashSet<>();11 12        for (int r = 0; r < numRows; r++) {13            for (int c = 0; c < grid[r].length; c++) {14                int val = grid[r][c];15                valueSet.add(val);16                locations.computeIfAbsent(val, k -> new ArrayList<>()).add(r);17            }18        }19 20        uniqueValues = new ArrayList<>(valueSet);21        Collections.sort(uniqueValues, Collections.reverseOrder());22 23        memo = new int[uniqueValues.size()][1 << numRows];24        for (int[] row : memo) {25            Arrays.fill(row, -1);26        }27 28        return solve(0, 0);29    }30 31    private int solve(int k, int usedRowsMask) {32        if (k == uniqueValues.size()) {33            return 0;34        }35 36        if (memo[k][usedRowsMask] != -1) {37            return memo[k][usedRowsMask];38        }39 40        // Option 1: Skip the current value41        int maxScore = solve(k + 1, usedRowsMask);42 43        // Option 2: Try to use the current value44        int currentValue = uniqueValues.get(k);45        if (locations.containsKey(currentValue)) {46            for (int row : locations.get(currentValue)) {47                // Check if the row is not used yet48                if ((usedRowsMask & (1 << row)) == 0) {49                    // Use this value in this row50                    maxScore = Math.max(maxScore, currentValue + solve(k + 1, usedRowsMask | (1 << row)));51                }52            }53        }54 55        return memo[k][usedRowsMask] = maxScore;56    }57}