What is the core dynamic programming pattern used in Maximum Score From Grid Operations?

It uses state transition DP where each state represents a column and the blackened rows, tracking score impact efficiently.

How do I determine which row to apply an operation on in a column?

Consider all possible rows for each column and use DP to select the row that maximizes the total score based on previous column states.

Can this problem be solved greedily instead of DP?

No, because each operation affects future scoring, a greedy approach may miss optimal sequences. State transition DP ensures correctness.

What is the expected time complexity for this problem?

Time complexity is roughly O(n * 2^n) due to iterating over all column masks and rows for state transitions.

Are there any constraints on grid values I should be aware of?

Yes, each grid[i][j] is between 0 and 10^9, and n ranges from 1 to 100, which affects mask size and DP feasibility.

#3225

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

网格图操作后的最大分数

给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到…

数组动态规划矩阵前缀和

题目描述

给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。

如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。

请你返回执行任意次操作以后，最终网格图的最大总分数。

示例 1：

输入：grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]

输出：11

解释：

第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。

示例 2：

输入：grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]

输出：94

解释：

我们对第 1 ，2 ，3 列分别从上往下染黑色到第 1 ，4， 0 行。最后网格图总分为 grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] 等于 94 。

提示：

1 <= n == grid.length <= 100
n == grid[i].length
0 <= grid[i][j] <= 10⁹

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	complexity depends on the number of columns n and the possible masks for rows, roughly O(n * 2^n), and space complexity is proportional to the number of masks stored for DP, also O(2^n * n).
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect an efficient state representation for column operations.
question_mark
Look for correct handling of row masks and adjacent white cell scoring.
question_mark
Check that DP avoids recomputing identical column sequences.

warning

常见陷阱

外企场景

error
Ignoring the effect of previous operations on scoring white cells.
error
Not properly encoding or updating masks, leading to incorrect DP states.
error
Overlooking edge cases where no operations are optimal for certain columns.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute maximum score when operations can also color entire rows.
arrow_right_alt
Allow diagonal adjacency instead of only horizontal for scoring.
arrow_right_alt
Consider grids where some cells cannot be blackened due to constraints.

help

常见问题

外企场景

继续练习

#3212 统计 X 和 Y 频数相等的子矩阵数量 #3250 单调数组对的数目 I #3251 单调数组对的数目 II