What is the best approach for Minimum Number of Operations to Satisfy Conditions?

Use state transition dynamic programming row by row, tracking the minimal operations for each possible cell value.

Can this problem be solved without dynamic programming?

Brute-force approaches are possible but inefficient; DP ensures minimal operations without redundant computation.

How do I handle large grids efficiently?

Optimize space by storing only the previous row's DP values and prune impossible transitions.

Why is state definition critical in this DP problem?

Incorrect state leads to double-counting operations or missing valid transitions, yielding wrong minimum counts.

Does changing a single cell affect the whole DP solution?

Yes, each cell influences possible next states, so proper transition accounting is essential for correctness.

#3122

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

使矩阵满足条件的最少操作次数

给你一个大小为 m x n 的二维矩形 grid 。每次操作中，你可以将任一格子的值修改为任意非负整数。完成所有操作后，你需要确保每个格子 grid[i][j] 的值满足：如果下面相邻格子存在的话，它们的值相等，也就是 grid[i][j] == grid[i + 1][j] （如果存…

数组动态规划矩阵

题目描述

给你一个大小为 m x n 的二维矩形 grid 。每次操作中，你可以将任一格子的值修改为任意非负整数。完成所有操作后，你需要确保每个格子 grid[i][j] 的值满足：

如果下面相邻格子存在的话，它们的值相等，也就是 grid[i][j] == grid[i + 1][j]（如果存在）。
如果右边相邻格子存在的话，它们的值不相等，也就是 grid[i][j] != grid[i][j + 1]（如果存在）。

请你返回需要的最少操作数目。

示例 1：

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

输出：0

解释：

矩阵中所有格子已经满足要求。

示例 2：

输入：grid = [[1,1,1],[0,0,0]]

输出：3

解释：

将矩阵变成 [[1,0,1],[1,0,1]] ，它满足所有要求，需要 3 次操作：

将 grid[1][0] 变为 1 。
将 grid[0][1] 变为 0 。
将 grid[1][2] 变为 1 。

示例 3：

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

输出：2

解释：

这个矩阵只有一列，我们可以通过 2 次操作将所有格子里的值变为 1 。

提示：

1 <= n, m <= 1000
0 <= grid[i][j] <= 9

lightbulb

解题思路

方法一：动态规划

我们注意到，矩阵中格子的值只有 $10$ 种可能，题目需要我们求出每一列数字相同，且相邻列数字不同的最小操作次数。那么我们只需要考虑将数字修改为 $0$ 到 $9$ 的情况即可。

我们定义状态 $f[i][j]$ 表示前 $[0,..i]$ 列数字，且第 $i$ 列数字为 $j$ 的最小操作次数。那么我们可以得到状态转移方程：

f[i][j] = \min_{k \neq j} f[i-1][k] + m - \textit{cnt}[j]

其中 $\textit{cnt}[j]$ 表示第 $i$ 列数字为 $j$ 的个数。

最后我们只需要求出 $f[n-1][j]$ 的最小值即可。

时间复杂度 $O(n \times (m + C^2))$ ，空间复杂度 $O(n \times C)$ 。其中 $m$ 和 $n$ 分别表示矩阵的行数和列数；而 $C$ 表示数字的种类数，这里 $C = 10$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[inf] * 10 for _ in range(n)]
        for i in range(n):
            cnt = [0] * 10
            for j in range(m):
                cnt[grid[j][i]] += 1
            if i == 0:
                for j in range(10):
                    f[i][j] = m - cnt[j]
            else:
                for j in range(10):
                    for k in range(10):
                        if k != j:
                            f[i][j] = min(f[i][j], f[i - 1][k] + m - cnt[j])
        return min(f[-1])

speed

复杂度分析

指标	值
时间	complexity depends on m, n, and the number of possible values per cell, typically O(m _n_ k^2) for k value options. Space complexity is O(n*k) if optimized row by row.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect candidates to define DP states clearly for each row and value.
question_mark
Look for correct handling of cell transitions while minimizing operations.
question_mark
Watch for approaches that avoid redundant computation across large grids.

warning

常见陷阱

外企场景

error
Ignoring state dependencies between rows, which leads to overcounted operations.
error
Failing to optimize space usage, storing full DP for all rows unnecessarily.
error
Misapplying operations count when a cell already satisfies the conditions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change grid conditions, e.g., increase-decrease patterns or parity requirements.
arrow_right_alt
Restrict the allowed cell values to a smaller subset, affecting DP transitions.
arrow_right_alt
Allow diagonal or adjacent cells to affect validity, increasing state complexity.

help

常见问题

外企场景

继续练习

#3148 矩阵中的最大得分 #3225 网格图操作后的最大分数 #3256 放三个车的价值之和最大 I