#3276

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Select Cells in Grid With Maximum Score

Optimize selection of grid cells using state transition dynamic programming to maximize total sum efficiently.

array dynamic programming bit manipulation matrix bitmask

Problem Statement

You are given a 2D matrix grid filled with positive integers. You must select one or more cells such that each selection respects valid transitions between rows and columns.

The goal is to maximize the sum of all selected cells. Constraints include grid dimensions up to 10x10 and values up to 100, requiring an approach that efficiently explores valid selections using state transitions.

Examples

Example 1

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

Output: 8

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

Example 2

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

Output: 15

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

Solution Approach

Sort and Track Cells

Sort all cells in descending order by value while keeping their original positions. This allows focusing on high-value cells first and simplifies state management for transitions.

Dynamic Programming with State Masks

Use bitmasks to represent selected cells in each row. Update states iteratively, combining previous row states with current candidates, ensuring valid selections while calculating cumulative sums.

Optimize Transitions

Prune invalid or dominated states to reduce computation. Only retain states that can lead to a higher total score, ensuring efficient exploration of the selection space for maximum score.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the number of rows, columns, and possible state masks. Worst-case complexity is exponential in row size due to bitmask combinations, but pruning high-value paths reduces practical runtime.

What Interviewers Usually Probe

Look for the candidate to sort cells by value and track positions correctly.
Watch if the candidate efficiently uses bitmask dynamic programming to represent row states.
Check if invalid transitions between rows are handled and dominated states are pruned.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly map sorted cells back to original grid positions.
Not pruning dominated states, causing unnecessary exponential computation.
Overlooking transitions that violate row or column selection rules, leading to incorrect totals.

Follow-up variants

Maximize score with restrictions on adjacent cell selection.
Extend to 3D matrices with similar state transition logic.
Compute maximum score while minimizing the number of selected cells.

FAQ

What is the main pattern used in Select Cells in Grid With Maximum Score?

The problem primarily uses state transition dynamic programming, tracking selected cells with masks or arrays.

Can I select any number of cells in the grid?

Yes, you can select one or more cells, but each selection must respect row and column transition rules.

How do I optimize space and time for this problem?

Use bitmasking for row states and prune dominated or invalid states to reduce unnecessary computation.

Why is sorting cells by value helpful?

Sorting helps prioritize high-value cells first and simplifies tracking original positions for valid state transitions.

What is a common mistake in DP for this problem?

A common mistake is ignoring invalid transitions or failing to update states correctly, which results in underestimating the maximum score.

terminal

Solution

Solution 1: State Compression Dynamic Programming

We define $f[i][j]$ to represent the maximum score when selecting numbers from $[1,..i]$ and the state of the rows corresponding to the selected numbers is $j$. Initially, $f[i][j] = 0$, and the answer is $f[\textit{mx}][2^m - 1]$, where $\textit{mx}$ represents the maximum value in the matrix, and $m$ represents the number of rows in the matrix.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        g = defaultdict(set)
        mx = 0
        for i, row in enumerate(grid):
            for x in row:
                g[x].add(i)
                mx = max(mx, x)
        m = len(grid)
        f = [[0] * (1 << m) for _ in range(mx + 1)]
        for i in range(1, mx + 1):
            for j in range(1 << m):
                f[i][j] = f[i - 1][j]
                for k in g[i]:
                    if j >> k & 1:
                        f[i][j] = max(f[i][j], f[i - 1][j ^ 1 << k] + i)
        return f[-1][-1]

Continue Practicing

#3376 minimum time to break locks i #3393 count paths with the given xor value #3149 find the minimum cost array permutation