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.

#3276

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

选择矩阵中单元格的最大得分

给你一个由正整数构成的二维矩阵 grid 。你需要从矩阵中选择一个或多个单元格，选中的单元格应满足以下条件：所选单元格中的任意两个单元格都不会处于矩阵的同一行。所选单元格的值互不相同。你的得分为所选单元格值的总和。返回你能获得的最大得分。示例 1：输入： grid …

数组动态规划位运算矩阵位掩码

题目描述

给你一个由正整数构成的二维矩阵 grid。

你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件：

所选单元格中的任意两个单元格都不会处于矩阵的 同一行。
所选单元格的值 互不相同。

你的得分为所选单元格值的总和。

返回你能获得的最大得分。

示例 1：

输入： grid = [[1,2,3],[4,3,2],[1,1,1]]

输出： 8

解释：

选择上图中用彩色标记的单元格，对应的值分别为 1、3 和 4 。

示例 2：

输入： grid = [[8,7,6],[8,3,2]]

输出： 15

解释：

选择上图中用彩色标记的单元格，对应的值分别为 7 和 8 。

提示：

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

lightbulb

解题思路

方法一：状态压缩动态规划

我们定义 $f[i][j]$ 表示在 $[1,..i]$ 的数中进行选择，且选择的数对应的行的状态为 $j$ 时的最大得分。初始时 $f[i][j] = 0$ ，答案为 $f[\textit{mx}][2^m - 1]$ 。其中 $\textit{mx}$ 表示矩阵中的最大值，而 $m$ 表示矩阵的行数。

我们首先对矩阵进行预处理，使用一个哈希表 $g$ 记录每个数对应的行的集合。然后我们可以使用状态压缩动态规划的方法求解答案。

对于状态 $f[i][j]$ ，我们可以不选择 $i$ 这个数，此时 $f[i][j] = f[i-1][j]$ ；也可以选择 $i$ 这个数，此时我们需要枚举 $i$ 对应的行的集合 $g[i]$ 中的每一个行 $k$ ，如果 $j$ 的第 $k$ 位为 $1$ ，则说明我们可以选择 $i$ 这个数，此时 $f[i][j] = \max(f[i][j], f[i-1][j \oplus 2^k] + i)$ 。

最后我们返回 $f[\textit{mx}][2^m - 1]$ 即可。

时间复杂度 $O(m \times 2^m \times \textit{mx})$ ，空间复杂度 $O(\textit{mx} \times 2^m)$ 。其中 $m$ 为矩阵的行数，而 $\textit{mx}$ 为矩阵中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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]

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#3376 破解锁的最少时间 I #3393 统计异或值为给定值的路径数目 #3149 找出分数最低的排列