题目描述
给你一个大小为 m x n
的二维矩形 grid
。每次 操作 中,你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后,你需要确保每个格子 grid[i][j]
的值满足:
- 如果下面相邻格子存在的话,它们的值相等,也就是
grid[i][j] == grid[i + 1][j]
(如果存在)。 - 如果右边相邻格子存在的话,它们的值不相等,也就是
grid[i][j] != grid[i][j + 1]
(如果存在)。
请你返回需要的 最少 操作数目。
样例
输入:grid = [[1,0,2],[1,0,2]]
输出:0
解释:
矩阵中所有格子已经满足要求。
输入: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 。
输入:grid = [[1],[2],[3]]
输出:2
解释:
这个矩阵只有一列,我们可以通过 2 次操作将所有格子里的值变为 1。
限制
1 <= n, m <= 1000
0 <= grid[i][j] <= 9
算法1
(动态规划) $O(mn + nu^2)$
- 可以证明,修改的数字一定还是在 $[0, 9]$ 中。如果不是的话,可以将非 $[0, 9]$ 的那一列修改为 $[0, 9]$ 中的某个数字,且答案不会变差。
- 设状态 $f(i, j)$ 表示遍历了前 $i$ 列,且最后一列修改为数字 $j$ 的最小操作次数。其中 $i$ 的范围为 $[0, n - 1]$;$j$ 的范围是 $[0, 9]$。
- 初始时 $f(0, j) = cost(0, j)$,其余为正无穷待定。其中 $cost(i, j)$ 为将第 $i$ 列修改为 $j$ 的代价,可以预处理提前计算。
- 转移时,对于 $f(i, j)$,枚举 $k \in [0, 9]$。当 $j \neq k$ 时,转移 $f(i, j) = \min(f(i, j), f(i - 1, k) + cost(i, j))$。
- 最终答案为 $\min(f(n - 1, j))$。
时间复杂度
- 预处理的时间复杂度为 $O(mn + nu)$。
- 动态规划的状态数为 $O(nu)$,转移时间为 $O(u)$。
- 故总时间复杂度为 $O(mn + nu^2)$。其中 $u$ 为原格子中最大可能的数字范围。
空间复杂度
- 需要 $O(nu)$ 的额外空间存储预处理数组和动态规划的状态。
C++ 代码
class Solution {
public:
int minimumOperations(vector<vector<int>>& grid) {
const int m = grid.size(), n = grid[0].size();
vector<vector<int>> cnt(n, vector<int>(10, 0));
for (int j = 0; j < n; j++)
for (int i = 0; i < m; i++)
++cnt[j][grid[i][j]];
vector<vector<int>> cost(n, vector<int>(10));
for (int j = 0; j < n; j++) {
int tot = 0;
for (int c = 0; c < 10; c++)
tot += cnt[j][c];
for (int c = 0; c < 10; c++)
cost[j][c] = tot - cnt[j][c];
}
vector<vector<int>> f(n, vector<int>(10, INT_MAX));
f[0] = cost[0];
for (int i = 1; i < n; i++)
for (int j = 0; j < 10; j++)
for (int k = 0; k < 10; k++)
if (j != k)
f[i][j] = min(f[i][j], f[i - 1][k] + cost[i][j]);
int ans = INT_MAX;
for (int c = 0; c < 10; c++)
ans = min(ans, f[n - 1][c]);
return ans;
}
};
算法2
(动态规划) $O(n(m + u))$
- 可以进一步优化算法 1。
- 设状态 $f(i, 1)$ 表示遍历了前 $i$ 列后的最小值以及在最小值的前提下第 $i$ 列的取值,$f(i, 2)$ 表示遍历了前 $i$ 列后的次小值。其中次小值可能等于最小值。
- 初始时,$f(0, 1) = (0, -1)$,$f(0, 2) = 0$。
- 转移时,对于当前列,枚举当前这一列选择的数字 $c$。如果选择的 $c$ 和上一列最小值的选择不同,则使用上一列的最小值更新当前列的最小值和次小值。否则,使用上一列的次小值更新当前列的最小值和次小值。
- 最终答案为 $f(n, 1)$。
时间复杂度
- 动态规划的状态数为 $O(n)$,转移时间为 $O(m + u)$。
- 故总时间复杂度为 $O(n(m + u))$。其中 $u$ 为原格子中最大可能的数字范围。
空间复杂度
- 由于每个状态仅与上一个状态相关,可以使用若干个变量替代数组表示状态。
- 统计每种数字的出现次数的空间复杂度为 $O(u)$。
- 故总时间复杂度为 $O(u)$。
C++ 代码
class Solution {
public:
int minimumOperations(vector<vector<int>>& grid) {
const int m = grid.size(), n = grid[0].size();
int f1 = 0, pre = -1, f2 = 0;
for (int j = 0; j < n; j++) {
vector<int> cnt(10, 0);
for (int i = 0; i < m; i++)
++cnt[grid[i][j]];
int tot = 0;
for (int c = 0; c < 10; c++)
tot += cnt[c];
int g1 = INT_MAX, t, g2 = INT_MAX;
for (int c = 0; c < 10; c++) {
int val = tot - cnt[c];
if (c != pre) val += f1;
else val += f2;
if (g1 > val) {
g2 = g1; g1 = val; t = c;
} else if (g2 > val) {
g2 = val;
}
}
f1 = g1; pre = t; f2 = g2;
}
return f1;
}
};